首页 > 代码库 > poj1035（Spell checker）
poj1035（Spell checker）
题目地址：Spell checker
题目大意：
给你一个关于字符串的字典，让你根据字典里的字符串判断输入字符串的正确性。如果字符串不正确，可以通过以下的操作来输出字符串的可能性：1.可以替换一个字符，2.可以删除一个字符，3.可以添加一个字符。如果满足以上操作，说明都算是字符串的可能性，然后输出。
解题思路：
判断四种情况即可，如果正确直接输出，如果出现1、2、3这几种情况，先将字符串存到一个字符数组里s[N][N]。如果全部判断完，没有正确性，输出可能性的字符串。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {-1,1,0,0}; 25 const int d1y[]= {0,0,-1,1}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 char s1[10001][16],s[10001][16]; 38 char s2[51][16]; 39 int main() 40 { 41 memset(s1,0,sizeof(s1)); 42 memset(s2,0,sizeof(s2)); 43 memset(s,0,sizeof(s)); 44 int m,n; 45 int i,j,k; 46 for(i=0;; i++) 47 { 48 scanf("%s",s1[i]); 49 m=i; 50 if (s1[i][0]==‘#‘) 51 break; 52 53 } 54 for(i=0;; i++) 55 { 56 scanf("%s",s2[i]); 57 n=i; 58 if (s2[i][0]==‘#‘) 59 break; 60 } 61 for(i=0; i<n; i++) 62 { 63 int len1=strlen(s2[i]); 64 65 int flag=0; 66 int d=0,h; 67 for(j=0; j<m; j++) 68 { 69 int cnt=0; 70 int len2=strlen(s1[j]); 71 int ce=len1-len2; 72 if (ce>1||ce<-1) 73 continue; 74 for(k=0,h=0; k<len1;) 75 { 76 if (s2[i][k]!=s1[j][h]&&len1>len2) 77 { 78 k++; 79 continue; 80 } 81 if (s2[i][k]!=s1[j][h]&&len1<len2) 82 { 83 h++; 84 if (h>=len2) 85 break; 86 continue; 87 } 88 if (s2[i][k]==s1[j][h]) 89 { 90 cnt++; 91 } 92 k++; 93 h++; 94 } 95 if (cnt==len1&&len1==len2) 96 { 97 flag=1; 98 break; 99 }100 else if (cnt==len1&&len1<len2)101 {102 flag=2;103 strcpy(s[d],s1[j]);104 d++;105 }106 else if (cnt==len2&&len1>len2)107 {108 flag=3;109 strcpy(s[d],s1[j]);110 d++;111 }112 else if (cnt==len2-1&&len1==len2)113 {114 flag=4;115 strcpy(s[d],s1[j]);116 d++;117 }118 }119 if (flag==1)120 printf("%s is correct\n",s2[i]);121 else122 {123 printf("%s:",s2[i]);124 for(j=0; j<d; j++)125 printf(" %s",s[j]);126 printf("\n");127 }128 129 }130 return 0;131 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。