AC自动机

AC自动机

十一月 01, 2021

AC自动机

概念描述：

AC自动机：（一种可以自动AC的机器），指的是一个文本串和若干个模式串看看这些模式串是否在文本串上被匹配（不需要管有几次，只要出现过就行）

核心思想：

fail指针

fail指针（这是早期oier们针对此题的一个指针的定义，没有多么高级，只是说明当你匹配成功或者失败后，你要去向何处）在trie上的一些应用来简化

trie树

直接把一个字符串一棵树上，把它们相同的部分连在一起，方便统一处理

trie树

trie树是一种很暴力但是很有用的一种数据结构

trie树是维护一棵树，它的每个节点都会有一些儿子，当我们插入一个新的字符串时，会从第一位开始找，看看树上是否已经有了这个节点，如果找到了就去它的儿子节点去找它的下一位，如果没有就对于这个新的节点建一个新的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct ZPK{//AωR2020 txdy
    int son[26];
    int num=0,flag=0;
}trie[N];
int tot;
inline void insert(char s[]){
    int u=1;
    for(int i=0;s[i];i++){
       	int v=s[i]-'a';
        if(!trie[u].son[v]) trie[u].son[v]=++tot;
        u=trie[u].son[v];
    }
    trie[u].num++;
}

这就是基本思想和代码了，每次读入一个字符串，直接insert即可

总而言之，言而总之：

$\Huge 有路找路走，没路自己开路走$

这是我学习trie树的一点点经验

get_fail

先放上来一个图（来源）

首先我们要先get一下fail指针的具体含义：

如果说一个点$i$的$fail$指针指向$j$，那么$root$到$j$一定是$root$到$i$这个字符串的前缀

那么我们一个字符的fail指针可能指向很多个数

我们还是拿上面的图举例子

$i$:4 $j$:7
$root$到$i$的字符串是“ABC”
$root$到$j$的字符串是“BC”
“BC”是“ABC”的一个后缀
“C”也是“ABC”的一个后缀
所以$i$的$Fail$指针指向$j$，意味着:

我们的$fail$指针指向的应该还得是这些后缀中$\text{dep}$最大的那个

这个$fail$指针看起来好牛逼啊

那么我们怎么办get到这个$fail$呢

我们想到了一些问题，对于字符串ABC和BC来说，其实我们

完全不需要去进行从后往前的枚举，我们要牢牢记得我们是建了一个trie树的

我们从上往下进行时，我们首先可以确定一件事情就是我们的$fail$指针指向的那个点的$\text{dep}$一定币当前节点小，所以我们首先可以确定第一层的点的fail都是指向节点$\text{root}$的

我们考虑中间一个点$i$的$\text{fa}$的$fail$指针指的是$\Large Fail$

如果$Fail$有和$i$相等的儿子的话那么就让$i$的$fail$值指向那个点，因为我们要维护若干个用父亲的$fail$，所以用$\text{bfs}$可能对于本题更为合适

然后我们再来看一个图（截自OI-wiki）

找到 6 的父结点 5，$fail[5]=10$。然而 10 结点没有字母 s 连出的边；继续跳到 10 的 $fail$指针，fail[10]=5。发现 0 结点有字母 s 连出的边，指向 7 结点；所以$fail[6]=7$。

实现细节与技巧

  1. 我们可以直接将每个点连到0号节点，然后我们将0号节点的所有儿子指向$root$一节点

  2. 如果$trie[u]$的儿子$i$是空的，那么我们可以将那个节点设为$Fail$的(值和$i$相同)的儿子。保证存在性，就算是0也可以成功返回到根，因为0的所有儿子都是根。

  3. 无论$Fail$存不存在和$i$值相同的儿子$j$，我们都可以将$i$的$fail$指向$j$，原因是处理$i$时$j$已经处理好了。

  4. 实现时不记父亲，我们直接让父亲更新儿子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getfail(){
    for(int i=0;i<26;i++) trie[0].son[i]=1;
    q.push(1);
    trie[1].fail=0;//将rt压入队列
    while(!q.empty()){
       	int u=q.front(),v=q.pop();
        for(int i=0;i<26;i++){
            int Fail=trie[u].fail;
            int v=trie[u].son[i];
            if(!v){
                trie[u].son[i]=trie[Fail].son[i];
                continue;
            }
            else{
                trie[v].fail=trie[Fail].son[i];
            	q.push(v);
            }
        }
    }
}

查询：

求出了$fail$指针后，如果一个字符串匹配成功，那么他的$fail$肯定也成功，它的$fail$的$fail$也可以成功，经过的点累加flag，标记为-1，然后我们跑的时候就不会被重复计算了。（也可以这么理解，如果你跑过这个点了，它的fail会使它一路跳到根，你会发现其实它们都是不需要的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int query(char* s){
	int u=1,ans=0,len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-'a';
		int k=trie[u].son[v];		//跳Fail
        
		while(k>1 && trie[k].flag!=-1){//经过就不统计了
			ans+=trie[k].flag,trie[k].flag=-1;	
             //累加上这个位置的模式串个数，标记该点已经经过
			k=trie[k].fail;			//继续跳Fail
		}
        
		u=trie[u].son[v];
	}
	return ans;
}

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=3e6+5;
queue<int> q;

template <typename T>
void read(T &x){
    x=0; char c=getchar(); int f=0;
    for(; !isdigit(c); c=getchar()) f |= c=='-';
    for(; isdigit(c); c=getchar()) x = x*10+(c^48);
    if(f) x = -x;
}
template <typename T>
void write(T &x,char ch){
    if(x<0) putchar('-'), x = -x;
    static short st[30],tp;
    do st[++tp] = x%10, x/=10; while(x);
    while(tp) putchar(st[tp--] | 48);
    putchar(ch);
}


struct ZPK{
    int num,fail;
    int son[30];
}trie[N];
int n,tot;
inline void insert(char s[],int len){
    int u=0;
    for(int i=0;i<len;i++){
        int v=s[i]-'a';
        if(!trie[u].son[v]) trie[u].son[v]=++tot;
        u=trie[u].son[v];
    }
    trie[u].num++;
}

inline void getfail(){
    for(int i=0;i<26;i++){
        if(trie[0].son[i]) q.push(trie[0].son[i]);
    }
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=0;i<26;i++){
            int v=trie[u].son[i];
            int Fail=trie[u].fail;
            if(!v) trie[u].son[i]=trie[Fail].son[i];
            else trie[v].fail=trie[Fail].son[i],q.push(v);
        }
    }
}

inline int query(char s[],int len){
    int u=0,ans=0;
    for(int i=0;i<len;i++){
        int v=s[i]-'a';
        int k=trie[u].son[v];
        while(k && trie[k].num!=-1){
            ans+=trie[k].num;
            trie[k].num=-1;
            k=trie[k].fail;
        }
        u=trie[u].son[v];
    }
    return ans;
}

char s[N];

int main(){
    read(n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        int len=strlen(s);
        insert(s,len);
    }
    getfail();
    memset(s,'\0',sizeof(s));
    scanf("%s",s);
    int len=strlen(s);
    int ans=query(s,len);
    write(ans,'\n');
    return 0; 
}

加强版

刚才我们问的是一个字符串是否在文本串中出现，

现在我们换一个问法，问你哪个字符串出现次数最多，是多少,并输出该字符串

然后我们给每个店的num直接改成这个点所对应的id，每次这个id++就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
struct ZPK{
    int son[26];
    int num,fail;
}trie[N];
int tot;
int ed[N];

inline void insert(int now,char c[]){
    int u=0,len=strlen(c);
    for(int i=0;i<len;i++){
        int v=c[i]-'a';
        if(!trie[u].son[v]) trie[u].son[v]=++tot;
        u=trie[u].son[v];
    }
    trie[u].num=now;
}

inline void getfail(){
    queue<int> q;
    for(int i=0;i<26;i++) if(trie[0].son[i]) q.push(trie[0].son[i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            int v=trie[u].son[i];
            int Fail=trie[u].fail;
            if(!v) trie[u].son[i]=trie[Fail].son[i];
            else trie[v].fail=trie[Fail].son[i],q.push(v);
        }
    }
}

inline void query(char c[]){
    int len=strlen(c);
    int u=0;
    for(int i=0;i<len;i++){
        int v=c[i]-'a';
        int k=trie[u].son[v];
        while(k){
            if(trie[k].num) ed[trie[k].num]++;
            k=trie[k].fail;
        }
        u=trie[u].son[v];
    }
}


inline void clear(){
    memset(ed,0,sizeof(ed));
    memset(trie,0,sizeof(trie));
    tot=0;
}

int n;
int main(){
    while(cin>>n && n){
        char s[200][100];
        for(int i=1;i<=n;i++){
            scanf("%s",s[i]);
            insert(i,s[i]);
        }
        getfail();
        scanf("%s",s[n+1]);
        query(s[n+1]);
        int ans=0;
        for(int i=1;i<=tot;i++) ans=max(ans,ed[i]);
        printf("%d\n",ans);
        for(int i=1;i<=tot;i++) if(ed[i]==ans) printf("%s\n",s[i]);
        clear();

    }
    return 0;
}

二次加强版