Hat’s Words HDU - 1247 字典树

 1 #include<bits/stdc++.h>
 2 #include<string>
 3 using namespace std;
 4 const int maxn=50005+5;
 5 struct Trie{
 6     int ch[maxn][28];
 7     int size;
 8     bool num[maxn];
 9     void init(){
10         memset(ch,0,sizeof(ch));
11         memset(num,0,sizeof(num));
12         size=1;
13     }
14     void insert(char*s){
15         int i=0,rc=0;
16         for( ;s[i]!='\0';i++){
17             int id=s[i]-'a';
18             if(ch[rc][id]==0){
19                 ch[rc][id]=size++;
20             }
21             rc=ch[rc][id];
22         }
23         num[rc]=1;
24     }
25     bool find(char*s){
26         int i=0,rc=0;
27         for(;s[i]!='\0';i++){
28             int id=s[i]-'a';
29             if(ch[rc][id]==0){
30                 return 0;
31             }
32             rc=ch[rc][id];
33         }
34         return num[rc];
35     }
36 
37 }trie;
38 char temp[60000][1000];
39 char s1[1000],s2[1000];
40 int main(){
41     int n=0;
42     trie.init();
43     while(scanf("%s",temp[n])==1){
44         //cout<<1<<endl;
45         n++;
46         trie.insert(temp[n-1]);
47     }
48     for(int i=0;i<n;i++){
49         int len=strlen(temp[i]);
50         for(int j=1;j<len-1;j++){
51             for(int k=0;k<j;k++){
52                 s1[k]=temp[i][k];
53             }
54             s1[j]='\0';
55           for(int k=j;k<len;k++)s2[k-j]=temp[i][k];
56           s2[len-j]='\0';
57             if(trie.find(s1)&&trie.find(s2)){
58                 printf("%s\n",temp[i]);
59                 break;
60             }
61         }
62     }
63     return 0;
64 }