AC 自动机

harmis_yz

5个月前发布

『我从来没有会过任何串串科技。』

AC 自动机

相当于多个 KMP。也就是多个模板字符串上搞某种匹配问题。

建 AC 自动机

假设我有 \(n\) 个字符串为 \(abc,bcd,bd,c\)（\(n=4\)）。

首先我们对 \(n\) 个字符串建立 Trie 树。长这样：【图】。

如果我们有个匹配串为 \(abcdbc\)，那么在这棵 Trie 树上暴力匹配会似。但是当我们匹配完 \(abc\) 这个串之后直接跳到 \(bcd\) 对应的 \(c\)，就可以大大节省时间复杂度。那么这里称一个节点 \(x\) 失配之后跳到的节点 \(y\) 为 \(x\) 的失配指针对应的点。在例子中 \(abc\) 的 \(c\) 对应节点的失配指针所对的节点就是 \(bcd\) 的 \(c\)。

对于失配指针，有个性质：如果 \(x\) 的失配指针指向 \(y\)，那么 \(root \to y\) 形成的字符串应为 \(root \to x\) 形成的字符串的后缀。那么我们就可以找失配指针了，失配指针应该是在 Trie 上 \(root \to y\) 为 \(root \to x\) 后缀的 \(y\) 中，最大的 \(dep_y\) 对应的点。

现在我们来求失配指针。首先，第一层的点的失配指针为 \(root\)，第 \(i\) 层的失配指针的 \(dep\) 一定小于 \(i\)。那么求 \(x\) 的失配指针的时候只需要看 \(x\) 的父亲的失配指针对应的点 \(y\) 的那个和 \(x\) 相同值的点了（1）。如果不存在相同值的点，那就不存在了，因为如果存在，那么它的父亲一定会有这个出边，又因为 Trie 上不存在两个不同节点 \(root\) 到它形成的字符串相同，所以不可能。如果节点 \(x\) 没有值为 \(y\) 的儿子，那么就让它的儿子变成 \(x\) 的失配指针的那个儿子（2）。

哦，我是不是说错了。我们的（1）是没有正确性的，但是如果我们加上（2）之后就有了，那个证明是唐的，删了。自行理解。

建 AC 自动机的时候可以按照深度 BFS，这样对于每个 \(x\)，我们都一定知道它父亲的失配指针了。为了方便，我们建一个虚点 \(0\)，让 \(0\) 的所有出边指向 \(root\) 节点 \(1\)，然后 \(1\) 的失配指针指向虚点。

il void build(){//建 AC 自动机
	queue<int> qu;qu.push(1),tr[1].fail=0;
	for(re int i=0;i<26;++i) tr[0].ch[i]=1;
	while(!qu.empty()){
		int u=qu.front();qu.pop();
		for(re int i=0;i<26;++i){
			int v=tr[u].ch[i];
			int fail=tr[u].fail;
			if(!v) tr[u].ch[i]=tr[fail].ch[i];
			else tr[v].fail=tr[fail].ch[i],qu.push(v);
		}
	}
	return ;
}

不难观察到，我们 AC 自动机相当于弄了两个东西出来，一个是 fail 树，一个是 DAG。fail 树保证了每个节点的父亲在 Trie 上一定是它的后缀，那么节点 \(x\) 的祖先也都是 \(x\) 在 Trie 上的后缀了。然后建出来的 DAG 貌似没什么用。

例题

P5357 【模板】AC 自动机

我们把 fail 树建出来，那么一个节点 \(x\) 的出现次数就应该是它的子树 \(siz\) 和。因为它是任意一个后代的前缀。而我们把一个匹配串拿去匹配的时候，是将它的每个前缀对应 Trie 上的最长后缀的那个节点记录次数，所以算出来是对的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    il int F(int n,int a,int b,int c){
        //sum{|_ (ai+b)/c _| i:0~n}
        if(!n) return b/c;
        if(!a) return (n+1)*(b/c);
        if(a>=c||b>=c){
            int x=a/b,y=b/c;
            return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
        }
        int m=(a*n+b)/c;
        return n*m+F(m-1,c,c-b+1,a);
    }
    struct lb{
        int d[64];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x,void(0);
            }
            return ;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=2e5+10;
struct Trie{
	int ch[26],fail;
}tr[N];
int idx=1,id[N];
int siz[N];
vector<int> e[N];

il void insert(string s,int k){
	int u=1;
	for(re int i=0;i<s.size();++i){
		if(!tr[u].ch[s[i]-'a']) tr[u].ch[s[i]-'a']=++idx;
		u=tr[u].ch[s[i]-'a'];
	}
	id[k]=u;
	return ;
}
il void build(){
	queue<int> qu;qu.push(1),tr[1].fail=0;
	for(re int i=0;i<26;++i) tr[0].ch[i]=1;
	while(!qu.empty()){
		int u=qu.front();qu.pop();
		for(re int i=0;i<26;++i){
			int v=tr[u].ch[i];
			int fail=tr[u].fail;
			if(!v) tr[u].ch[i]=tr[fail].ch[i];
			else tr[v].fail=tr[fail].ch[i],qu.push(v);
		}
	}
	return ;
} 
il void match(string s){
	int u=1;
	for(re int i=0;i<s.size();++i){
		u=tr[u].ch[s[i]-'a'];
		++siz[u];
	}
	return ;
}
il void dfs(int u){
	for(auto v:e[u]) dfs(v),siz[u]+=siz[v];
	return ;
}

il void solve(){
	int n=rd;
	for(re int i=1;i<=n;++i){
		string s;cin>>s;
		insert(s,i);
	}
	build();
	for(re int i=1;i<=idx;++i) e[tr[i].fail].push_back(i);
	string t;cin>>t;
	match(t),dfs(0);
	for(re int i=1;i<=n;++i) printf("%lld\n",siz[id[i]]);
    return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    int t=1;while(t--)
    solve();
    return 0;
}