题解 P3808 【【模板】AC自动机(简单版)】
hicc0305
2018-08-02 21:00:21
蒟蒻终于把~~WA~~ AC自动机打出来了。。。
## AC自动机讲解
AC自动机简单来说就是Tire Tree + ~~看毛片~~KMP,也就是~~在~~树上~~看毛片~~KMP。
AC自动机用来解决多模式串匹配,也就是给好几个子串,一个很长很长很长很长很长的母串,让你处理一些问题,比如什么子串出现的次数之类的。
怎么做咧?
你先把所有的子串丢到Trie上,比如四个字符串:abcd,abd,bcd,cd,建立如下图Trie树:
![](https://cdn.luogu.com.cn/upload/pic/26389.png)
然后我们就要树上看毛片了!
和KMP中的next数组很像,我们定义fail数组,fail[i]为与以i节点为结尾的串的后缀有最大公共长度的前缀的结尾编号。这句话是不是有点绕orz。
我们来分析一下什么意思:对于以d结尾的子串abcd,不存在任何一个其他子串的前缀与abcd匹配,但bcd与abcd的后缀bcd匹配,这是匹配到的最长情况,于是这个d上的fail指针就指向bcd上的d。然后,如果没有找到任何一个前缀与当前串的任何一个后缀一样的话,那么fail只能指到根了。和KMP的原理一样,fail跳到的地方必然这个子串的前面不用再比较了,因为根据fail的定义,它的已经前缀已经被比较过并且匹配了。只用再往后比就行了。放一下图:
![](https://cdn.luogu.com.cn/upload/pic/26392.png)
记num[i]为以i节点为结尾的子串有几个,我们对于每个子串,都在这个子串的结尾,把num++,以方便以后跳来跳去的时候统计。匹配到当前节点,就加上当前节点的num,当然,加过了就不要再加了,因为这道题并不是统计所有子串出现的总数,而是有多少子串出现了。
那么。。对于匹配的时候,当前节点配不下去了怎么办?比如我们尝试匹配abcde,abcd都顺利匹配了,这时候我们发现d并没有e这个节点,那么我们就跳到d的fail指针,也就是bcd上的d,还是没有e,那么继续,到cd上的d,还是没有,只能到根了,还是没有。。。那么。。。就没有了。我们处理的时候,就可以把abcd上的d的不存在的儿子,指向d的fail指针的这个儿子,好像还是有点绕。。
那么继续上图,(这里的e点都为虚线,实际上是没有的):
![](https://cdn.luogu.com.cn/upload/pic/26396.png)
也就是说,我们在不断尝试,有没有其他前缀后面跟着e的。这样处理之后,就简单方便多了。
------------
## 代码
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0;
char tmp[1000100];
struct node
{
int fail,num;
int ch[30];
}tr[1000100];
int q[1000100];
void build()//建立Trie树
{
int len=strlen(tmp),u=0;
for(int i=0;i<len;i++)
{
int s=tmp[i]-'a';
if(tr[u].ch[s]==0) tr[u].ch[s]=++cnt;
u=tr[u].ch[s];
}
tr[u].num++;
}
void get_fail()
{
int l=0,r=0;
for(int i=0;i<26;i++)
if(tr[0].ch[i]!=0)
{
tr[tr[0].ch[i]].fail=0;
q[++r]=tr[0].ch[i];
}
while(l<r)
{
int u=q[++l];
for(int i=0;i<26;i++)
{
int v=tr[u].ch[i];
if(v)
{
tr[v].fail=tr[tr[u].fail].ch[i];//处理fail指针,是它父亲的fail指针的i儿子
q[++r]=v;
}
else tr[u].ch[i]=tr[tr[u].fail].ch[i];//处理所说的“虚指针”,WA了好几次因为把这里的tr[u].ch[i]也替换成v了。。
}
}
}
int AC()
{
int len=strlen(tmp);
int u=0,ans=0;
for(int i=0;i<len;i++)
{
int s=tmp[i]-'a';
u=tr[u].ch[s];
int v=u;
while(v && tr[v].num!=-1)
{
ans+=tr[v].num;
tr[v].num=-1;//加过了之后就不用再加了
v=tr[v].fail;
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
build();
}
tr[0].fail=0;
get_fail();
scanf("%s",tmp);
printf("%d",AC());
return 0;
}
```
你会发现代码和yyb大佬的很像,因为我是看了yyb的题解才打出来的。。yyb的很清楚,所以我放上来只是凑个长度的没错