AC自动机 模板与简单讲解 模板题:贴瓷砖

    xiaoxiao2023-11-21  5

    引入

    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个小写字母,瓷砖不能旋转也不能被分割开来,瓷砖只能贴在跟它身上的字母完全一样的地方,允许瓷砖重叠,并且同一种瓷砖的数量是无穷的。 问街道有多少字母(地方)不能被瓷砖覆盖。

    Input

    第一行输入街道长度N(1<=N<=300,000)。 第二行输入N个英文小写字母描述街道的情况。 第三行输入M(1<=M<=5000),表示瓷砖的种类。 接下来M行,每行描述一种瓷砖,长度为Li(1<=Li<=5000),全部由小写字母构成。

    Output

    输出有多少个地方不能被瓷砖覆盖。

    Sample Input

    输入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]];//求up } } } 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
    最新回复(0)