【模板】AC自动机加强版

题目大意：给定 N 个模式串和一个文本串，求每个模式串在文本串中出现的次数。

题解：文本串在自动机上匹配的过程中，记录下自动机上每一个状态被访问的次数。对于访问到的节点 i，则状态 i 的后缀中存在的匹配串的出现次数都要增加 1。若每次都暴力跳 fail 树的话，复杂度无法得到保证。观察发现，对于每一个模式串，能够对其答案产生贡献的状态一定是 fail 树上的，以该模式串节点为根节点的子树中的节点表示的状态。因此，将 fail 树显示建立出来，在文本串匹配结束后做一次 dfs 即可求出所有的模式串对应的答案了。时间复杂度还是 \(O(N+M)\)。

注意：模式串中可能存在相同的串，若单纯记录自动机上每个节点对应的字符串会 WA 掉（后一个把前一个覆盖掉了）。因此，需要记录每个模式串对应着自动机上的哪个状态节点才行。

代码如下

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn=2e5+10;

const int maxm=2e6+10;

int n;

int trie[maxn][26],tot=1,match[maxn],fail[maxn],sz[maxn];

vector<int> G[maxn];

queue<int> q;

void insert(char *s,int id){

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

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

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

        if(!trie[now][ch])trie[now][ch]=++tot;

        now=trie[now][ch];

    }

    match[id]=now;

}

void build(){

    for(int i=0;i<26;i++)trie[0][i]=1;

    q.push(1);

    while(q.size()){

        int u=q.front();q.pop();

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

            if(trie[u][i]){

                fail[trie[u][i]]=trie[fail[u]][i];

                q.push(trie[u][i]);

            }else{

                trie[u][i]=trie[fail[u]][i];

            }

        }

    }

}

void query(char *s){

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

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

        now=trie[now][s[i]-'a'];

        ++sz[now];

    }

}

void dfs(int u){

	for(auto v:G[u]){

		dfs(v);

		sz[u]+=sz[v];

	}

}

char s[maxm];

void read_and_parse(){

    scanf("%d",&n);

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

        scanf("%s",s);

        insert(s,i);

    }

    build();

    scanf("%s",s);

}

void solve(){

    query(s);

    for(int i=2;i<=tot;i++)G[fail[i]].pb(i);

    dfs(1);

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

}

int main(){

    read_and_parse();

    solve();

    return 0;

}

巴特西

【模板】AC自动机加强版

最新文章

热门文章