AC 自动机(Aho–Corasick 算法)与字符串匹配问题(HDU 2222 Keywords Search)

/ 0评 /

据说很多公司都有这样一道面试题:给你几个 G 的字符串,让你想办法快速地找出其中的很多个需要和谐的敏感词。
这个问题里,如果“需要和谐的字符串”称为“模式串”,“待被查的字符串”称为文本串。对于这样的问题,如果暴力做,复杂度就是 \Theta(N \ast M \ast Len)……用 AC 自动机这种高级的算法,可以在 \Theta (N) 左右复杂度内得出答案。Excited!

这个 AC 自动机可不是 Accepted 自动机……其实是“Aho–Corasick 算法”,是由 Alfred V. Aho 和 Margaret J.Corasick 发明的字符串搜索算法,

维基百科上说:

该算法主要依靠构造一个有限状态机(类似于在一个trie树中添加失配指针)来实现。这些额外的失配指针允许在查找字符串失败时进行回退(例如设Trie树的单词cat匹配失败,但是在Trie树中存在另一个单词cart,失配指针就会指向前缀ca),转向某前缀的其他分支,免于重复匹配前缀,提高算法效率。

是不是听起来就很高级!

AC 自动机与 KMP

其实按照 AC 自动机的思想可以发现:这其实就是树上 KMP,即 Trie 树与 KMP 算法的结合。网上的几乎各路题解都说:“在学习 AC 自动机前要先掌握 Trie 树与 KMP”……

但是其实学 AC 自动机不需要掌握 KMP。

AC 自动机的实际应用

前面已经提到:据说很多公司都有这样一道面试题(据说是美团 2015 面试题?):给你几个 G 的字符串,让你想办法快速地找出其中的很多个需要和谐的敏感词。这几乎是很多互联网公司要做的事情。这种东西用 AC 自动机来做就会大大提高效率。

据说,UNIX 系统中的一个命令 fgrep 就是以 AC 自动机算法作为基础实现的。高级!

失配指针(Fail 指针)

首先我们对于所有的模式串,构造一棵 Trie 树(即字典树)。举个例子,假设文本串是 shers,模式串分别是:sherherser,那么构造的 Trie 树是这样的:

从 Trie 树到 Trie 图

在查询的时候,查询的文本串是 sher,自然一直往最左边一路;走的时候可以发现前面四个一直匹配;当走到左边一颗子树的最底下的 R 结点,再走发现 R 没有儿子了,也就是说不再匹配。那么这时候就称为 R 失配了
那么当 R 失配了,我们下一步要从哪里开始走呢?我们想要找一段 sher 的最长后缀,这样才能保证这段后缀仍然是文本串的子串,并且答案最优。显然,第二棵子树里 h - e -r 这条路径是最优解。当 R 失配后,我们可以直接跳到左起第二棵子树的 R 结点,这样保证 hersher最长后缀
所以最左边一条子树的 R 结点的失配指针(fail 指针)指向左起第二棵子树的 R。类似地,造出所有失配指针,用虚线连接:

构造失配指针之后,后面的处理就很方便了。

构造失配指针

怎么构造失配指针呢?

首先我们设 fail[x] 表示 x 的失配指针。假设当前的结点不存在 c 儿子了:

因此,用一个 BFS 就可以方便地构造出失配指针了。

但是这样找 fail 指针可能会很慢,因为要一直 fail fail 地找,十分暴力,有没有优化方法呢?
答案是肯定的。可以方便地通过 Trie 图实现。

还可以更快

仔细思考,其实我们可以当 x 没有儿子时直接把 x 与 fail[x] 连边,反正都是要走过去的。然后就可以将所有空儿子都连上后继结点。这样对于每次寻找失配指针,我们都可以 O(1) 找到,不需要每次都 fail 去找了。

代码如下:

inline void BuildFail(){ // Build Mismatch Pointer
    for (int i=0;i<26;i++) if (c[0][i]) que.push(c[0][i]);
    while (!que.empty()){
        int x=que.front();que.pop();
        for (int i=0;i<26;i++) if (c[x][i]){
            fail[c[x][i]]=c[fail[x]][i];
            que.push(c[x][i]);
        } else c[x][i]=c[fail[x]][i];
    }
}

查询的实现

查询其实很方便了,我们只需要按照文本串在字典树上走,把走过的点的 value 标记为 -1。因为任意点只会走到一次。没走到一个点就一直 fail、累计即可。

判断一个数 x 是否为 -1 的高端写法是:如果 ~ x==false,则 x 为 -1。因为 -1 是 32 位整数里每位都为 1,按位取反就是 0 了。

代码如下:

inline int query(char s[]){
    int len=strlen(s),ret=0,x=0;
    for (int i=0;i<len;i++){
        int now=s[i]-'a';
        x=c[x][now];
        for (int t=x;t&&~val[t];t=fail[t]) ret+=val[t],val[t]=-1;
    }
    return ret;
}

拓展应用

通过上面的 Trie 图可以发现,AC 自动机几乎把字符串题目转化为了图论题目。这样我们就可以结合树形 DP、结合 DFS 序等等等等衍生出一大堆用途。这也是 AC 自动机的意义之一了。

(未完待续……)


模板题

当然可以先去做洛谷上的模板题了~

这也是道模板题:HDU 2222 Keywords Search

代码

HDU 2222

// Aho–Corasick Algorithm
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1000005,maxlen=55,maxlen_q=1000005;
int T,n,cnt=0;
int c[maxn][30],fail[maxn],val[maxn];
char s[maxlen],q[maxlen_q];
queue<int> que;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void init(){
    cnt=0;
    memset(c,0,sizeof(c));
    memset(fail,0,sizeof(fail));
    memset(val,0,sizeof(val));
}
inline void insert(char s[]){ // Insert a word to Trie Tree
    int len=strlen(s),x=0;
    for (int i=0;i<len;i++){
        int now=s[i]-'a';
        if (!c[x][now]) c[x][now]=++cnt;
        x=c[x][now];
    }
    val[x]++;
}
inline void BuildFail(){ // Build Mismatch Pointer
    for (int i=0;i<26;i++) if (c[0][i]) que.push(c[0][i]);
    while (!que.empty()){
        int x=que.front();que.pop();
        for (int i=0;i<26;i++) if (c[x][i]){
            fail[c[x][i]]=c[fail[x]][i];
            que.push(c[x][i]);
        } else c[x][i]=c[fail[x]][i];
    }
}
inline int query(char s[]){
    int len=strlen(s),ret=0,x=0;
    for (int i=0;i<len;i++){
        int now=s[i]-'a';
        x=c[x][now];
        for (int t=x;t&&~val[t];t=fail[t]) ret+=val[t],val[t]=-1;
    }
    return ret;
}
int main(){
    T=read();
    while (T--){
        n=read();init();
        for (int i=1;i<=n;i++) scanf("%s",s),insert(s);
        BuildFail();
        scanf("%s",q);
        printf("%d\n",query(q));
    }
    return 0;
}

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/aho-corasick-algorithm/


发表评论

电子邮件地址不会被公开。 必填项已用*标注