AC自动机

OI 笔记 算法 字符串

一句话总结

AC自动机 = Trie + KMP

主要流程

注意：之后的讲解中刻意混淆了“指针”与“指针指向的元素”

这里，以一组数据为例：

模板串：

she 
he 
say 
shr 
her 

文本串

yasherhs

本文将以图片+代码的形式呈现，如有不理解之处，手动模拟尝试即可。

数据结构

int Trie_[MAXN_][26]; // Trie树
int Fail_[MAXN_]; // 失配指针
int Cnt_[MAXN_]; // 以该节点为单词结尾的单词数
int tot_;
int q_[MAXN_ + 10], qhd_, qtl_;

建立Trie树

void add(char *S_) { // 添加模板串
    int pos_ = 0; // 记录当前节点位置，从根开始
    int len_ = strlen(S_); // 插入的串的长度
    for (Rint i = 0; i < len_; ++i) { // 逐字符检查
        if (!Trie_[ pos_ ][ S_[i] - 'a' ]) // 如果没有这个位置
            Trie_[pos_][ S_[i] - 'a'] = ++tot_; // 申请这个位置
        pos_ = Trie_[pos_][ S_[i] - 'a']; // 向下走
    }
    Cnt_[pos_]++; // 记录出现次数
}

建立失配指针

void build() { // 构建失配指针(Fail[])
    // 广度优先遍历
    qhd_ = qtl_ = 0;
    Fail_[0] = 0;
    // 首先处理模板串起点的失配指针(=0)
    for (Rint i = 0; i < 26; ++i) {
        if (Trie_[0][i]) { // 如果有该节点
            Fail_[ Trie_[0][i] ] = 0;
            q_[qtl_++ % QLEN_] = Trie_[0][i]; // 入队
        }
    }
    int tmp_;
    while (qhd_ != qtl_) {
        tmp_ = q_[qhd_++ % QLEN_];
        for (int i = 0; i < 26; ++i) { // 遍历子节点
            if (Trie_[tmp_][i]) { // 该子节点存在
                Fail_[ Trie_[tmp_][i] ] = Trie_[ Fail_[tmp_] ][i];
                // 失配指针为 当前节点的失配指针 的子节点
                q_[qtl_++ % QLEN_] = Trie_[tmp_][i];
            } else { // 该子节点不存在
                // 直接连接到失配指针的子节点
                // 现在，trie树成了trie图
                Trie_[tmp_][i] = Trie_[ Fail_[tmp_] ][i];
            }
        }
    }
}

这里还有一个小优化：将trie树变成trie图，减少失配指针跳跃次数。

查询

极其类似KMP
(这里图示有误，will fix soon)

// 统计文本串中出现了多少种模板串
int query(char* S_) {
    int ans_ = 0, now_ = 0;
    int len_ = strlen(S_);
    for (Rint i = 0; i < len_; ++i) {
        now_ = Trie_[now_][S_[i] - 'a'];
        for (register unsigned int t = now_; t && ~Cnt_[t]; t = Fail_[t]) {
            ans_ += Cnt_[t];
            Cnt_[t] = -1;
        }
    }
    return ans_;
}

例题

[POI2000]病毒

这个题堪称经典AC自动机例题，做完后对AC自动机的了解又上了一个层次。

考虑文本串匹配的过程，如果一直无法匹配到单词终点，那么，AC自动机上一定有环，参考下图理解环的意义。

该图中，蓝色边为原始trie树，黑色边为fail指针，红色边为trie图改进，这里为了使图没有那么乱，没有为末尾节点建立trie图，图中的环已经被加粗。

要注意的是，一个点的失配指针如果是一个单词末尾，那么这个点也是单词末尾，对应程序中的：

val[ trie[tmp][i] ] |= val[ trie[fail[tmp]][i] ];

code：

#define Rint register int
int trie[M][2], fail[M], val[M], tot;
char s[M];
int n;
int q[M], qhd, qtl;
int flag, vis[M], ins[M];
inline void add(char *s);
inline void build() {
    for (Rint i = 0; i <= 1; ++i) {
        if (trie[0][i]) {
            fail[ trie[0][i] ] = 0;
            q[qtl++] = trie[0][i];
        }
    }
    int tmp;
    while (qhd != qtl) {
        tmp = q[qhd++];
        for (Rint i = 0; i <= 1; ++i) {
            if (trie[tmp][i]) {
                fail[ trie[tmp][i] ] = trie[ fail[tmp] ][i];
                val[ trie[tmp][i] ] |= val[ trie[fail[tmp]][i] ];
                q[qtl++] = trie[tmp][i];
            } else {
                trie[tmp][i] = trie[ fail[tmp] ][i];
            }
        }
    }
}
void dfs(int f) {
    if (flag) return;
    ins[f] = 1;
    vis[f] = 1;
    for (int i = 0; i <= 1; ++i) {
        if (trie[f][i] && !val[ trie[f][i] ]) {
            if (ins[ trie[f][i] ]) {
                flag = 1;
                break;
            }
            if (!vis[ trie[f][i] ]) dfs(trie[f][i]);
        }
    }
    ins[f] = 0;
}
int main() {
// read and build
    dfs(0);
    if (flag) printf("TAK\n");
    else printf("NIE\n");
    return 0; 
}