[算法模版]AC自动机

基础内容

板子不再赘述，OI-WIKI有详细讲解。

\(query\)函数则是遍历文本串的所有位置，在文本串的每个位置都沿着\(fail\)跳到根，将沿途所有元素答案++。意义在于累计所有以当前字符为结尾的所有模式串的答案。看代码就能很容易的理解。

另外\(e[i]\)记录的是第\(t\)个模式串结尾是哪个节点（所有节点均有唯一的编号）。

贴个P5357 【模板】AC自动机（二次加强版）板子：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#define maxn (int)(2e6+10000)

int ch[(int)(2e5+1000)][30],fail[maxn],cnt,e[maxn],nex[maxn],n,myque[maxn],ans[maxn],head[maxn],idx;

using namespace std;

char s[(int)(2e6+1)];

char data[maxn];

struct gg {

    int u,v,next;

}side[maxn*2];

void ins(int u,int v) {

    side[++idx]=(gg){u,v,head[u]};head[u]=idx;

}

void init() {

    memset(ch,0,sizeof(ch));

    memset(fail,0,sizeof(fail));

    memset(e,0,sizeof(e));

    memset(nex,0,sizeof(nex));

    memset(ans,0,sizeof(ans));

    cnt=0;

}

void insert(int t) {

    int now=0,len=strlen(s);

    for(int i=0;i<len;i++) {

        int num=s[i]-'a';

        if(!ch[now][num])ch[now][num]=++cnt;

        now=ch[now][num];

    }

    e[t]=now;

}

void build(){

    int l=0,r=0;

    for(int i=0;i<=26;i++)if(ch[0][i])myque[++r]=ch[0][i];

    while(l<r) {

        int now=myque[++l];ins(now,fail[now]),ins(fail[now],now);//确定now儿子的fail指针

        for(int i=0;i<=26;i++) {

            if(ch[now][i]) {

                myque[++r]=ch[now][i];

                fail[ch[now][i]]=ch[fail[now]][i];

                //   ins(ch[now][i],ch[fail[now]][i]);ins(ch[fail[now]][i],ch[now][i]);

            }

            else ch[now][i]=ch[fail[now]][i];

        }

    }

}

void query() {

    int now=0;

    for(int i=0;data[i];i++) {

        now=ch[now][data[i]-'a'];

        //for(int j=now;j;j=fail[j])ans[j]++;

        ans[now]++;

    }

}

void dfs(int x,int f) {

    for(int i=head[x];i;i=side[i].next) {

        int v=side[i].v;if(v==f)continue;

        dfs(v,x);

    }

    ans[f]+=ans[x];

}

int main() {

    init();

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%s", s);

        insert(i);

    }

    build();

    scanf("%s", data);

    query();//for(int i=cnt;i>=0;i--);

    dfs(0,0);

    //for(int i=cnt;i>=1;i--)ans[fail[i]]+=ans[i];

    for(int i=1;i<=n;i++)printf("%d\n",ans[e[i]]);

    return 0;

}

last优化(引自sclbgw7)

博主懒，就不造*了。原文链接见参考文献。

---

上述方法将建图+匹配的复杂度成功优化为了 $