HDU 1247 Hat’s Words（字典树）

http://acm.hdu.edu.cn/showproblem.php?pid=1247

题意：

给出一些单词，问哪些单词可以正好由其他的两个单词首尾相连而成。

思路：

先将所有单独插入字典树，然后对于每一个单词，枚举它的分割点，去字典树中查找是否具有这两个单词。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 50000+5;
 6 
 7 char s[maxn][105];
 8 int num = 0;
 9 
10 struct Trie
11 {
12     int son[26];
13     int ends;
14 }t[maxn*100];
15 
16 void init(int x)
17 {
18     t[x].ends = 0;
19     memset(t[x].son,0,sizeof(t[x].son));
20 }
21 
22 void insert(char* s)
23 {
24     int u = 0, n = strlen(s);
25     for(int i=0;i<n;i++)
26     {
27         int c = s[i]-'a';
28         if(!t[u].son[c])
29         {
30             num++;
31             init(num);
32             t[u].son[c] = num;
33         }
34         u = t[u].son[c];
35     }
36     t[u].ends = 1;
37 }
38 
39 bool query(char* s)
40 {
41     int u = 0, n = strlen(s);
42     for(int i=0;i<n;i++)
43     {
44         int c = s[i]-'a';
45         if(!t[u].son[c])  return false;
46         u = t[u].son[c];
47     }
48     if(t[u].ends == 1)  return true;
49     return false;
50 }
51 
52 int main()
53 {
54     //freopen("in.txt","r",stdin);
55     int tot = 0;
56     char s1[105],s2[105];
57     while(~scanf("%s",s[tot++])) insert(s[tot-1]);
58     for(int i=0;i<tot;i++)
59     {
60         int len = strlen(s[i]);
61         for(int j=1;j<len;j++)
62         {
63             memset(s1,0,sizeof(s1));
64             memset(s2,0,sizeof(s2));
65             strncpy(s1,s[i],j);
66             strncpy(s2,s[i]+j,len-j);
67             if(query(s1) && query(s2)) {printf("%s
",s[i]);break;}
68         }
69     }
70     return 0;
71 }