AC自动机
前置芝士:
回忆kmp
在 kmp
算法中,我们得到了一个
由于它的性质,可以用
这个算法只适用于一对一的字符串匹配,现在试图将问题扩大化:
给定一堆模式串
字典树构建
对于多个模式串,先给他构建字典树把它表示出来,没什么好说的。
void insert(string s)
{
int now=1;
for(char ch:s)
{
int c=ch-'a';
if(!son[now][c]) son[now][c]=++tot;
now=son[now][c];
}
++cnt[now];//这个节点是多少个模式串的终点
}
2
3
4
5
6
7
8
9
10
11
AC自动机构建
对于多串匹配,关键点还是在于一个类似
在字典树上沿着文本串
在多个串的时候,考虑的不仅仅是自己的
例如
S=xabcab
T1=xabd
T2=abca
2
3
当枚举到
当枚举到
我们把
左边的
那么
用 oiwiki 这张图再来解释:
这里的
因为如果目前的文本串已经前进到了
图中的黄色的边被称为失配指针
失配指针和
怎么建立这一套失配指针呢
先将直接与根节点相连的这一排的失配指针直接连到根节点。然后从这一排节点开始
枚举当前节点
如果节点
如果已知了
即
fail[son[now][c]]=son[fail[now]][c]
如果
为了方便,直接让
son[now][c]=son[fail[now]][c]
这样当失配的时候,就会自动找到失配指针指向的位置。
总体代码:
void build()
{
queue<int> q;
int now=1;
for(int c=0;c<26;++c) if(son[now][c])
{
fail[son[now][c]]=1;
q.push(son[now][c]);
}
while(!q.empty())
{
int now=q.front();q.pop();
for(int c=0;c<26;++c)
{
if(son[now][c])
{
fail[son[now][c]]=son[fail[now]][c];
q.push(son[now][c]);//将子节点入栈
}
else son[now][c]=son[fail[now]][c];//向fail寻找出边。
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
在进行多模式串匹配时,假如两个模式串,它们分别是
然后此时,文本串是
对于这种情况,每当到达一个节点,都要去遍历这个节点的
令
int query(string t)
{
int now=1,ans=0;
for(char ch:t)
{
int c=ch-'a';
now=son[now][c];
for(int p=now;p;p=fail[p]) ans+=cnt[p];
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
这样每一步都跳
当然这是有办法避免的,我们可以将满足
即
如果是询问每个模式串在文本串中出现多少次,可以在匹配时先不跳
在匹配完成后,用所有节点和
每个节点的真实被访问次数,是
练习题
P3121 [USACO15FEB] Censoring G