【OI之路】10字符串-5AC自动机

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

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

一、定义

这东西就是KMP思想和字典树的结合。

首先,对于多模问题,也就是对一个母串判断多个字符串是否是它的子串时,

(对于判断多个字符串是否是它的母串,kmp灰常优秀)

每个都做一次KMP显然是不合理的,同时为了减小空间,采用字典树

二、KMP思想

我主要用fail“指针”实现
在字典树中,假设现在有节点i,保证从【root到fail】路径上的字符串是从【root到i】的最长后缀
这样,当我们失配时,退而求其次,尝试匹配它的后缀
其实有种【树上kmp】的感觉

三、有关字典树

在每个节点中有一个变量s,我们对于字典树模板的修改和利用主要体现在这上面,可能还有一个布尔保证不再来。

四、从例题开始

Caioj1464
我采用clean是为了应对多组数据的情况,并且比全部直接初始化更灵活和更快
负责专题那家伙说求fail时放入队列的顺序并不重要,然后我就跟着用了bfs,至于dfs我没试过
注意solve中曾经有个BUG,就是应该每次都尝试引导k到fail那里,即使还没到字符串尾(这样才不会忽略掉包含的情况,例如abcd和bc,在abcd中计算),caioj的数据已经改进了~

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=1100000;
//*******************全局定义*******************
char s[MAXN];
//*******************实现*******************
struct Trie
{
int s;
int ch[26];
int fail;
}a[510000];
int cnt;
void clear(int x)
{
a[x].s=a[x].fail=0;
memset(a[x].ch,0,sizeof(a[x].ch));
}
void add()
{
int ln=strlen(s+1);
int now=0;
for(int i=1;i<=ln;i++)
{
int t=s[i]-'a';
if(!a[now].ch[t])
{
clear(++cnt);
a[now].ch[t]=cnt;
}
now=a[now].ch[t];
}
a[now].s++;
}
int lst[MAXN];
void getfail()
{
int tou=1,wei=2;lst[1]=0;
while(tou!=wei)
{
int x=lst[tou++];if(tou==MAXN) tou=1;
for(int i=0;i<26;i++)
{
int son=a[x].ch[i];
if(!son) continue;
if(x>0)//debug
{
int j=a[x].fail;
while(j>0 and !a[j].ch[i]) j=a[j].fail;
a[son].fail=a[j].ch[i];
}
lst[wei++]=son;if(wei==MAXN) wei=1;
}
}
}
int solve()
{
int ln=strlen(s+1);
int ans=0;
int now=0;
for(int i=1;i<=ln;i++)
{
int t=s[i]-'a';
while(now>0 and !a[now].ch[t]) now=a[now].fail;
now=a[now].ch[t];
if(now>0)
{
int tmp=now;//匹配了现在这个等同于匹配了其所有后缀
while(a[tmp].s>=0)
{
ans+=a[tmp].s;
a[tmp].s=-1;//阻断
tmp=a[tmp].fail;
}
}
}
return ans;
}
//*******************主函数*******************
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
clear(0);cnt=0;
while(n--)
{
scanf("%s",s+1);
add();
}
getfail();
scanf("%s",s+1);
printf("%d\n",solve());
}
}

五、练习

地图匹配
更全面的:Tag-AC自动机

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

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