简单的字符串查找题，暴力搜索就能过。
重点是细节，细节有没有！！！
爆搜差不多150毫秒，我建了一个长度哈希表，成了110毫秒。
下面是代码：
#include <stdio.h> #include <string.h> #include <stdlib.h> char dic[10005][18],s[20]; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } bool Change(int x) { int dif=0,i=0,y=strlen(s); //dif记录s与dic中在相同位置出现不同字符的个数 while(i!=y) { if(dic[x][i]!= s[i]) { dif++; if(dif>1) return false; } i++; } return true; } bool Del(int x) { int dif=0,i=0,j=0,y=strlen(s); //dif记录s与dic中在对应位置出现不同字符的个数 while(i!=y) { if(s[i]!= dic[x][j]) { j++; //dic后移一位再匹配 dif++; if(dif>1) return false; } else { i++; j++; } } return true; } bool Add(int x) { int dif=0,i=0,j=0,y=strlen(dic[x]); //dif记录s与dic中在对应位置出现不同字符的个数 while(j!=y) { if(s[i]!=dic[x][j]) { i++; //s后移一位再匹配 dif++; if(dif>1) return false; } else { i++; j++; } } return true; } int main() { int len[20][10005],head[20],i,j,k,n=0; memset(len,0,sizeof(len)); memset(head,0,sizeof(head)); while(scanf("%s",dic[n]),dic[n][0]!='#') { int l=strlen(dic[n]); len[l][head[l]]=n; head[l]++; n++; } while(scanf("%s",s),s[0]!='#') { int l=strlen(s),x,flat=0,a[10005],cut=0; for(i=0;i<head[l];i++) { flat=0; x=len[l][i]; if(!strcmp(s,dic[x])) { flat=1; break; } else if(Change(x)) { a[cut]=x; cut++; } } if(flat) { printf("%s is correct\n",s); } else { for(i=0;i<head[l+1];i++) { x=len[l+1][i]; if(Del(x)) { a[cut]=x; cut++; } } for(i=0;i<head[l-1];i++) { x=len[l-1][i]; if(Add(x)) { a[cut]=x; cut++; } } qsort(a,cut,sizeof(a[0]),cmp); printf("%s:",s); for(i=0;i<cut;i++) { printf(" %s",dic[a[i]]); } printf("\n"); } } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996812.html
