HDU 2846 Repository（字典树）

题目大意

给了 P(1<=P<=10000) 件商品的名字(名字长度不超过20)，现在有 Q(1<=Q<=100000) 个查询，每个询问是询问一个字符串，问的是所有的商品名字中，包含这个字串的名字的数量

做法分析

做法比较裸，先把所有的商品名字以及这些名字的后缀建立一棵字典树，利用后缀的思想

那么，很容易想到：一个给定的查询字符串，一定是这些所有的后缀的一个前缀

现在等于是问：以这个字符串为前缀的不同后缀的个数

在建立字典树的时候，对于数中的每个节点，都需要一个标记 cnt：表示从根节点到当前节点，路径上经过的字符形成的字符串，被多少个不同的单词的后缀覆盖过

举个例子：

有两个单词：aba 和 bc

他们的所有后缀是： aba(1) ba(1) a(1) bc(2) c(2) （括号中的数字表示这个后缀属于哪个单词）

那么，建立好的字典树就是：

怎么建树，其实很简单，大家稍微的想想就出来了

参考代码

HDU 2486

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 struct Tire
 9 {
10     struct Node
11     {
12         Node *next[26];
13         int cnt, flag;
14         Node()
15         {
16             for(int i=0; i<26; i++) next[i]=NULL;
17             cnt=0, flag=-1;
18         }
19     };
20 
21     Node *root;
22     Tire()
23     {
24         root=new Node();
25     }
26 
27     void Insert(char buff[], int s, int fg)
28     {
29         Node *u=root;
30         for(int i=s; buff[i]; i++)
31         {
32             int v=buff[i]-'a';
33             if(u->next[v]==NULL) u->next[v]=new Node();
34             u=u->next[v];
35             if(u->flag!=fg)
36             {
37                 u->cnt++;
38                 u->flag=fg;
39             }
40         }
41     }
42 
43     int Find(char buff[])
44     {
45         Node *u=root;
46         for(int i=0; buff[i]; i++)
47         {
48             int v=buff[i]-'a';
49             if(u->next[v]==NULL) return 0;
50             u=u->next[v];
51         }
52         return u->cnt;
53     }
54 } tree;
55 
56 char s[30];
57 int n;
58 
59 int main()
60 {
61     scanf("%d", &n);
62     for(int i=0; i<n; i++)
63     {
64         scanf("%s", s);
65         int t=(int)strlen(s);
66         for(int j=0; j<t; j++) tree.Insert(s, j, i);
67     }
68     scanf("%d", &n);
69     for(int i=0; i<n; i++)
70     {
71         scanf("%s", s);
72         printf("%d\n", tree.Find(s));
73     }
74     return 0;
75 }

AC通道

HDU 2846 Repository