Trie 集合
POJ 2418
题意：给你一堆字符串，然后按字典序输出，再输出他们出现的频率。
思路：trie。
#define N 1111111char in[N][22] ;char out[N] ;bool vis[11111] ;int insertanddelete(char *a , char *b){ int la = strlen(a) ; int lb = strlen(b) ; if(la <= lb)return 0 ; int nn = 0 ; int bb = 0 ; for (int i = 0 ; i < la ; i ++ ){ if(a[i] == b[bb]){ nn ++ ; bb ++ ; } else { continue ; } } if(nn == lb)return 1 ;return 0 ;}int replace(char *a ,char *b){ int la = strlen(a) ; int lb = strlen(b) ; if(la != lb)return 0 ; int nn = 0 ; for (int i = 0 ; i < la ; i ++ ){ if(a[i] != b[i])nn ++ ; } if(nn == 1)return 1 ;return 0 ;}int main(){ int num = 1 ; while(scanf("%s",in[num]) != EOF){ if(in[num][0] != '#'){ num ++ ; } else { while(scanf("%s",out) , out[0] != '#'){ bool flag = 0 ; mem(vis ,0) ; int lb = strlen(out) ; for (int i = 1 ; i < num ; i ++ ){ int la = strlen(in[i]) ; if(la == lb){ int xx = 0 ; for (int j = 0 ; j < la ; j ++ ){ if(in[i][j] != out[j]) xx ++ ; } if(xx == 0)flag = 1 ; if(flag)break ; } if(abs(la - lb) > 1)continue ; if(insertanddelete(in[i] , out) || insertanddelete(out , in[i]) || replace(in[i] , out)){ vis[i] = 1 ; } } if(flag){ printf("%s is correct\n",out) ; } else { printf("%s:",out) ; for (int i = 1 ; i < num ; i ++ )if(vis[i])printf(" %s",in[i]) ; puts("") ; } } } } return 0 ;}