引入
AC自动机是什么呢 首先要知道KMP,KMP是单字符串匹配 接下来要知道字典树,是用来存一堆字符串 AC自动机就是它们合起来:多字符串匹配
用一个网上很多人举的例子 在一篇文章中找出某些字符串出现的次数就是AC自动机的作用
建trie
fo(i,
1,m)
{
scanf(
"%s",t+
1);
scanf(
"\n");
int k=
1;
fo(j,
1,
strlen(t+
1))
{
int l=t[j]-
96;
if (c[k][l]==
0) c[k][l]=++tot;
deep[c[k][l]]=deep[k]+
1;k=c[k][l];
}
c[k][
0]=
1;
}
fail
KMP有个next数组 到了AC自动机,有个一样作用的fail数组 建fail的思想自己YY或找国家队论文,网上很多资料不靠谱 建fail程序
void buildfail()
{
int j=
1,h=
0;d[j]=
1;
for(;h<j;)
{
int k=d[++h],p=
0;
fo(i,
1,
26)
if(c[k][i]!=
0)
{
int p=c[k][i];
if(p)
{
int z=
fail[k];
while(z!=
0&&c[z][i]==
0) z=
fail[z];
fail[p]=c[z][i];
d[++j]=p;
}
fail[p]=(
fail[p]==
0)?
1:
fail[p];
up[p]=p;
}
}
}
用队列,c数组是trie,第二维就是代表26个字母
查询
查询也就差不多了,对于每一次都从fail链上走过即可
void query()
{
int k=1;
fo(i,1,n)
{
int j=s[i]-96;
while(k!=1 && c[k][j]==0) k=fail[k];
k=c[k][j];k=(k==0)?1:k;
while (p!=1)
{
if(c[p][0]==1) ans++;
p=fail[p];
如果不能重复的话就把c[p][0]标记为负数就行了
}
}
}
套上题目,灵活运用,加上各种优化。
模板题:贴瓷砖
Description
A镇的主街是由N个小写字母构成,镇长准备在上面贴瓷砖,瓷砖一共有M种,第i种上面有Li个小写字母,瓷砖不能旋转也不能被分割开来,瓷砖只能贴在跟它身上的字母完全一样的地方,允许瓷砖重叠,并且同一种瓷砖的数量是无穷的。 问街道有多少字母(地方)不能被瓷砖覆盖。
第一行输入街道长度N(1<=N<=300,000)。 第二行输入N个英文小写字母描述街道的情况。 第三行输入M(1<=M<=5000),表示瓷砖的种类。 接下来M行,每行描述一种瓷砖,长度为Li(1<=Li<=5000),全部由小写字母构成。
Output
输出有多少个地方不能被瓷砖覆盖。
输入1: 6 abcbab 2 cb cbab 输入2: 4 abab 2 bac baba 输入3: 6 abcabc 2 abca cab
Sample Output
输出1: 2 输出2: 4 输出3: 1
Data Constraint
N(1<=N<=300,000)
这题就是AC自动机的裸题
加个小优化:用up[x]表示x沿fail链上的第一个有值的点,这样就不用循环了 求答案就线段覆盖咯~~
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 301000
#define M 5010
using namespace std;
char s[N],t[M];
int n,m,fail[M*
1000],deep[M*
1000],c[M*
800][
28],ans[N][
2],bz[N],up[M*
1000],tot=
1,d[M*
1000];
void buildfail()
{
int j=
1,h=
0;d[j]=
1;
for(;h<j;)
{
int k=d[++h],p=
0;
fo(i,
1,
26)
if(c[k][i]!=
0)
{
int p=c[k][i];
if(p)
{
int z=fail[k];
while(z!=
0&&c[z][i]==
0) z=fail[z];
fail[p]=c[z][i];
d[++j]=p;
}
fail[p]=(fail[p]==
0)?
1:fail[p];
up[p]=p;
if(c[up[p]][
0]==
0&&up[p]!=
1) up[p]=up[fail[p]];
}
}
}
void query()
{
int k=
1;
fo(i,
1,n)
{
int j=s[i]-
96;
while(k!=
1 && c[k][j]==
0) k=fail[k];
k=c[k][j];k=(k==
0)?
1:k;
ans[++ans[
0][
0]][
0]=i;ans[ans[
0][
0]][
1]=deep[up[k]];
}
}
int main()
{
freopen(
"ACauto.in",
"r",stdin);
scanf(
"%d\n",&n);
scanf(
"%s",s+
1);
scanf(
"%d\n",&m);
fo(i,
1,m)
{
scanf(
"%s",t+
1);
scanf(
"\n");
int k=
1;
fo(j,
1,
strlen(t+
1))
{
int l=t[j]-
96;
if (c[k][l]==
0) c[k][l]=++tot;
deep[c[k][l]]=deep[k]+
1;k=c[k][l];
}
c[k][
0]=
1;
}
buildfail();
query();
fo(i,
1,ans[
0][
0])
{
bz[ans[i][
0]+
1]--;bz[ans[i][
0]-ans[i][
1]+
1]++;
}
int an=
0,jy=
0;
fo(i,
1,n)
{
jy+=bz[i];
if(jy==
0) an++;
}
printf(
"%d",an);
}
转载请注明原文地址: https://ju.6miu.com/read-1284166.html