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 ;}