HDOJ2846解题报告【字典树】

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2846

题目概述：

　　给你P个单词以及Q个询问，对于每个询问，回答一个整数，表示询问的字符串是多少个所给的单词的子串。

大致思路：

　　很容易看出是一个字典树的题，因为只要是子串都满足题意，所以在插入的时候需要多插入一些，例如：

　　　　对于单词abcd，则需要插入字符串abcd，bcd，cd，d；

　　然后插入的时候顺便统计一下个数，这样查询起来就当做正常的字典树查询就可以了。

　　需要注意的是，对于同一个字符串，插入子串时如果没有新建节点是不要使该节点统计的个数增加的。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <queue>
 9 #include <cstring>
10 #include <algorithm>
11 using namespace std;
12 
13 #define sacnf scanf
14 #define scnaf scanf
15 #define maxn 1000000
16 #define maxm 26
17 #define inf 1061109567
18 #define Eps 0.001
19 const double PI=acos(-1.0);
20 #define mod 1000000007
21 #define MAXNUM 10000
22 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
23 int Abs(int x) {return (x<0)?-x:x;}
24 typedef long long ll;
25 
26 struct node
27 {
28     int num;int cnt;
29     int next[maxm];
30 } tire[maxn];
31 
32 int c=1;
33 char s[maxm];
34 
35 void Insert(int root,char *s,int n)
36 {
37     while(*s!='')
38     {
39         int t=*s-'a';
40         if(tire[root].next[t]==-1)
41         {
42             int temp=c++;
43             for(int i=0;i<maxm;i++) tire[temp].next[i]=-1;
44             tire[temp].cnt=0;tire[root].num=n;
45             tire[root].next[t]=temp;
46         }
47         root=tire[root].next[t];
48         if(tire[root].num!=n) tire[root].cnt++;      //不需要增加个数的情况
49         tire[root].num=n;s++;
50     }
51 }
52 
53 int found(int root,char *s)
54 {
55     while(*s!='')
56     {
57         int t=*s-'a';
58         if(tire[root].next[t]==-1) return 0;
59         root=tire[root].next[t];s++;
60     }
61     return tire[root].cnt;
62 }
63 
64 int main()
65 {
66     //freopen("data.in","r",stdin);
67     //freopen("data.out","w",stdout);
68     //clock_t st=clock();
69     int root=0;
70     for(int i=0;i<maxm;i++) tire[root].next[i]=-1;
71     tire[root].num=0;tire[root].cnt=0;
72     int n;scanf("%d",&n);
73     for(int i=1;i<=n;i++)
74     {
75         scanf("%s",s);
76         int len=strlen(s);
77         for(int t=0;t<len;t++)
78             Insert(root,s+t,i);
79     }
80     scanf("%d",&n);
81     while(n--)
82     {
83         scanf("%s",s);
84         printf("%d
",found(root,s));
85     }
86     //clock_t ed=clock();
87     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
88     return 0;
89 }