AC自动机——多个kmp匹配

时间:2022-04-28 00:02:08

(并不能自动AC)

介绍:

Aho-Corasick automaton,最经典的处理多个模式串的匹配问题。

是kmp和字典树的结合。

 

精髓与灵魂:

①利用trie处理多个模式串

②引入fail指针。节点x的fail表示,trie中最大的某个前缀等于x到根节点字符串后缀的节点位置。

fail类比于kmp的nxt数组,可以在失配的时候,O(1)找到最大的可能能继续匹配的位置。

所以,ac自动机可看做多个kmp

 

 

步骤:(完整代码在下面)

①建trie树。插入模式串。

void ins(char *s){
        int len=strlen(s+1);
        int now=0;
        for(int i=1;i<=len;i++){
            int x=s[i]-'A';
            if(!a[now][x]) a[now][x]=++cnt;
            now=a[now][x];
        }
        exi[now]=1;
    }

②trie上建ac自动机。

void build(){
        queue<int>q;
        for(int i=0;i<26;i++){
            if(a[0][i]) fail[a[0][i]]=0,q.push(a[0][i]);
        }
        while(!q.empty()){
            int x=q.front();q.pop();
            exi[x]|=exi[fail[x]];
            for(int i=0;i<26;i++){
                if(a[x][i]){
                    fail[a[x][i]]=a[fail[x]][i];
                    q.push(a[x][i]);
                }
                else{
                    a[x][i]=a[fail[x]][i];    
                }
            }
        }
    }

用bfs来建造,并且,即时转移fail指针。

fail指针的转移正确性:

因为bfs是分层加入元素,而fail至少让字符串长度-1,所以之前的fail[x]的各种信息都处理完毕了。

并且,由于fail的定义,所以能在fail[x][i]往下转移,一定就是最优的。

 

这里有个小优化:

else{a[x][i]=a[fail[x]][i];}

如果x没有i这个儿子,那么就直接指向它fail指针位置的儿子。

这样子,在之后的if(a[x][i])中,可以直接走一次fail[x]的儿子就可以找到真正的fail[a[x][i]]了。

因为,如果fail没有这个儿子,不加这个优化还要继续跳fail,复杂度没有保证了。

这样,就类似于并查集的路径压缩思想,直接指到最长的有这个儿子的点了。

(语言表达不好,自行画图理解吧。。。)

 

完整代码:

struct node{
	int a[N*N][26],cnt;
	int fail[N*N];
	bool exi[N*N];
	void init(){
		memset(a,0,sizeof a);memset(exi,0,sizeof exi);
		cnt=0;memset(fail,0,sizeof fail);
	}
	void ins(char *s){
		int len=strlen(s+1);
		int now=0;
		for(int i=1;i<=len;i++){
			int x=s[i]-'A';
			if(!a[now][x]) a[now][x]=++cnt;
			now=a[now][x];
		}
		exi[now]=1;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++){
			if(a[0][i]) fail[a[0][i]]=0,q.push(a[0][i]);
		}
		while(!q.empty()){
			int x=q.front();q.pop();
			exi[x]|=exi[fail[x]];
			for(int i=0;i<26;i++){
				if(a[x][i]){
					fail[a[x][i]]=a[fail[x]][i];
					q.push(a[x][i]);
				}
				else{
					a[x][i]=a[fail[x]][i];	
				}
			}
		}
	}
}ac;

 

另外,我们ac自动机上节点上,也可以加上其他的标记。

 

例题:

[JSOI2007]文本生成器

Description:

给n个模式串,求有多少个长度为m的文章,至少包含一个模式串

Solution:

Ac自动机的标志很明显,多个模式串,一个主串。

Ac自动机dp的状态很套路,一般就是匹配到j位置,怎么怎么样。。

设f[i][j],前i个字符,匹配到AC自动机的j位置,没出现一个模式串的方案数。(最后总方案-没出现一个方案,差分)

每个点有一个exi布尔数组,表示匹配到这个点,这个点所代表的前缀(可以是一个完整模式串)是否已经包含了至少一个模式串。

插入的时候,末尾exi=1,bfs的时候,exi[x]|=exi[fail[x]]即可。正确性同bfs分层图性质。

然后判断,直接转移就好了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100+3;
const int mod=10007;
struct node{
    int a[N*N][26],cnt;
    int fail[N*N];
    bool exi[N*N];
    void init(){
        memset(a,0,sizeof a);memset(exi,0,sizeof exi);
        cnt=0;memset(fail,0,sizeof fail);
    }
    void ins(char *s){
        int len=strlen(s+1);
        int now=0;
        for(int i=1;i<=len;i++){
            int x=s[i]-'A';
            if(!a[now][x]) a[now][x]=++cnt;
            now=a[now][x];
        }
        exi[now]=1;
    }
    void build(){
        queue<int>q;
        for(int i=0;i<26;i++){
            if(a[0][i]) fail[a[0][i]]=0,q.push(a[0][i]);
        }
        while(!q.empty()){
            int x=q.front();q.pop();
            exi[x]|=exi[fail[x]];
            for(int i=0;i<26;i++){
                if(a[x][i]){
                    fail[a[x][i]]=a[fail[x]][i];
                    q.push(a[x][i]);
                }
                else{
                    a[x][i]=a[fail[x]][i];    
                }
            }
        }
    }
}ac;
int n,m;
int f[N][N*N];
char s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        ac.ins(s);
    }
    ac.build();
    int tot=ac.cnt;
    f[0][0]=1;
    for(int i=0;i<=m-1;i++){
        for(int j=0;j<=tot;j++){
            if(!ac.exi[j]){
                for(int k=0;k<26;k++){
                    if(!ac.exi[ac.a[j][k]]){
                        f[i+1][ac.a[j][k]]=(f[i+1][ac.a[j][k]]+f[i][j])%mod;
                    }
                }
            }
        }
    }
    long long ans=1;
    for(int i=1;i<=m;i++){
        ans=(ans*26)%mod;
    }
    for(int i=0;i<=tot;i++){
        if(!ac.exi[i]){
            ans=(ans-f[m][i]+mod)%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}

 

为什么要记录AC自动机上匹配到的状态呢?

因为,单纯记录这一位是哪个字符肯定不能判断是否包含。

而AC自动机本身的fail,就蕴含了所有的可能包含的位置。只要不断跳fail即可。

相当于该状态已经包罗万象。

因为fail的定义,也不会包含更多,不会包含更少。

所以对于匹配问题再适合不过了。

 

AC自动机dp出题人出烦了之后,

就开始出一些涉及AC自动机形态的题目,更贴近算法本身。

基本开刀处都是fail指针(AC自动机的精髓嘛)

 

[POI2000]病毒

这是一个利用fail指针构可能可以和trie树构成环的特性。从而构造出无限长的串。

[NOI2011]阿狸的打字机——AC自动机之fail树的利用

这个题目恰好相反,把fail树和trie树都利用起来,并且离线处理。

 

这两个题目都是值得思考总结的。都利用了fail的性质,但是都没有直接使用fail指针。妙哉!