【OI之路】10字符串-4字典树

一句精辟的话:字符串相关算法就是用来偷懒的 ——scy

更详细地解释:Manacher、莫队、fft、后缀数组、exkmp等各种算法,本质上都是尽量地利用子信息、残留信息

这东西属于数据结构,还是很有趣的……
这个的话我就不解释太多了,根据代码理解完全足够

简单的例题:统计前缀
Caioj1463
HDU1251

【题意】
给出很多个字符串(只有小写字母组成)和很多个提问串,统计出以某个提问串为前缀的字符串数量(单词本身也是自己的前缀).
【输入格式】
输入n,表示有n个字符串(n<=10000)
接下来n行,每行一个字符串,字符串度不超过10
输入m,表示有m个提问(m<=100)
第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
【输出格式】
对于每个提问,给出以该提问为前缀的字符串的数量.
【样例输入】
5
banana
band
bee
absolute
acm
4
ba
b
band
abc
【样例输出】
2
3
1
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//*******************定义*******************
struct Trie
{
int s,c[27];
}a[500010];
//*******************实现*******************
void clean(int x)
{
a[x].s=0;
for(int i=1;i<=26;i++) a[x].c[i]=-1;
}
char s[20];int len,k;
void add()
{
len=strlen(s+1);
int x=0;
for(int i=1;i<=len;i++)
{
int t=s[i]-'a'+1;
if(a[x].c[t]<0)
{
a[x].c[t]=++k;
clean(k);
}
x=a[x].c[t];
a[x].s++;
}
}
int solve()
{
len=strlen(s+1);
int x=0;
for(int i=1;i<=len;i++)
{
int t=s[i]-'a'+1;
if(a[x].c[t]<0) return 0;
x=a[x].c[t];
}
return a[x].s;
}
//*******************主函数*******************
int main(int argc, char *argv[])
{
clean(0);k=0;
int n;scanf("%d",&n);
while(n--)
{
scanf("%s",s+1);
add();
}
int m;scanf("%d",&m);
while(m--)
{
scanf("%s",s+1);
printf("%d\n",solve());
}
}

字典树练习:
HDU1075
HDU1800

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7385.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%