随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXSIZE 50001
 4 char str[MAXSIZE][100];
 5 struct Tries{
 6     int nodes;
 7     Tries *next[26];
 8     Tries(){
 9         nodes=0;
10         memset(next,NULL,sizeof(next));
11     }
12 };
13 Tries *tree=new Tries();
14 void insert(char word[]){
15     Tries *temp=tree;
16     int i=0;
17     while(word[i]){
18         int k=word[i]-'a';
19         if(temp->next[k]==NULL)
20             temp->next[k]=new Tries();
21         temp=temp->next[k];
22         i++;
23     }
24     temp->nodes++;
25 }
26 
27 bool visited(char word[]){
28     Tries *temp=tree;
29     int i=0;
30     while(word[i]){
31         int k=word[i]-'a';
32         if(temp->next[k]==NULL)
33             return false;
34         temp=temp->next[k];
35         if(temp->nodes&&word[i+1]=='\0')
36             return true;
37         i++;
38     }
39     return false;
40 }
41 
42 bool query(char word[]){
43     Tries *temp=tree;
44     int i=0;
45     while(word[i]){
46         int k=word[i]-'a';
47         if(temp->next[k]==NULL)
48             return false;
49         temp=temp->next[k];
50         if(temp->nodes&&visited(&word[i+1]))
51             return true;
52         i++;
53     }
54     return false;
55 }
56 int main(){
57     #ifndef ONLINE_JUDGE
58     freopen("in.txt","r",stdin);
59     #endif 
60     int j,i=0;
61     while(gets(str[i]))
62         insert(str[i++]);
63     for(j=0;j<i;j++)
64         if(query(str[j]))
65             puts(str[j]);
66     return 0;
67 }
posted on 2012-05-15 23:03 Leo.W 阅读(76) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理