hdu 1251統計難問（辞書ツリー）

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1251
難問を統計する
Time Limit：4000/2000 MS（Java/Others）    メモリLimit:1313137070/65535 K(Java/Others)Total Submission(s):25233    Accepted Submission(s)：10347
Problem Description
Ignatiusは最近難しい問題に遭いました。先生は彼に多くの単語を渡しました。（小文字だけで構成されています。重複した単語は現れません。）。今先生はある文字列を接頭語とする単語の数を統計してくださいと言いました。
 
 
Input
入力データの第一部は単语の表で、行ごとに一つの単语、単语の长さは10を超えないです。その代表は先生がIgnatiusに渡した単语で、一つの空行は単语の表の终わりを表します。
注意：この問題はテストデータのセットだけで、ファイルの最後まで処理します。
 
 
Output
各質問に対して、文字列をプレフィックスとする単語の数が与えられる。
 
 
Sample Input
bana
バンド
bee
absolute
acm
 
ば
b
バンド
abc
 
 
Sample Output
2
3
1
0
 
中国語の問題です。同じプレフィックスを見つけたのはいくつですか？
問題の構想を解きます：木を建てて、辞書の木のテンプレートのテーマ。
 
詳細はコードを参照してください
最初の種類はMapを使います

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 #include <cstring>
 5 #include <string>
 6 
 7 using namespace std;
 8 
 9 char str[110];
10 string ss;
11 char ch1[110],ch[110];
12 
13 int main()
14 {
15     map<string,int>qq;
16     //qq[string]=int;
17     while (gets(str))
18     {
19         int len=strlen(str);
20         if (len==0)
21             break;
22         int j;
23         for (int i=0;i<len;i++)
24         {
25             for (j=0;j<=i;j++)
26             {
27                 ch1[j]=str[j];
28             }
29             ch1[j]='\0';
30             ss.assign(ch1);
31             qq[ss]++;
32         }
33     }
34     while (~scanf("%s",&ch))
35     {
36         //cout<<1111111<<endl;
37         cout<<qq[ch]<<endl;
38     }
39     return 0;
40 }

 
二つ目は辞書の木です。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 struct node
10 {
11     int Count;
12     node *next[26];
13     node() //     
14     {
15         for (int i=0;i<26;i++)
16             next[i]=NULL;
17         Count=0;
18     }
19 };
20 
21 node *p,*root=new node();
22 void Insert(char *s)//     ，      
23 {
24     int i,k;
25     p=root;
26     for (i=0; s[i]!='\0'; i++)
27     {
28         k=s[i]-'a';
29         if (p->next[k]==NULL)
30             p->next[k]=new node();//        ，                , root next    k      
31         p=p->next[k];
32         p->Count++; //          
33     }
34 }
35 
36 int Search(char *s)
37 {
38     int i,k;
39     p=root;
40     for (i=0; s[i]!='\0'; i++)
41     {
42         k=s[i]-'a';
43         if (p->next[k]==NULL)//      ，    
44             return 0;
45         p=p->next[k];
46     }
47     /*if (s[i]!='\0')//s[i]!=0    
48         return 0;*/
49     return p->Count;
50 }
51 
52 int main()
53 {
54     char s[11];
55     while (gets(s))
56     {
57         int len=strlen(s);
58         if (len==0)
59             break;
60         Insert(s);
61     }
62     while (gets(s))
63     {
64         printf ("%d
",Search(s));
65     }
66     return 0;
67 }