Trie树与AC自动机

作为现阶段的学习中个人应有的常识，AC自动机形象的来讲就是在Trie树上跑的一个KMP。由此，我们就先来谈一谈Trie树。(有图)

1. Trie树

又称单词查找树，字典树，一般用于字符串的匹配。它利用公共的字符串前缀进行查询，减少了无谓的操作，是空间换时间的经典算法。举例：

此图包含了{"to", "tea", "ted", "ten", "a", "i", "in", "inn"}这些字符串。

Trie树的基本性质可以归纳为：

1. 根节点不包含字符，除根节点意外每个节点只包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。

Trie树有两个基本操作，一为插入，二为删除，且两者复杂度均为\(O(len)\)（其中$len = $ 字符串长度）。

我们以对五个串aaaa,abb,aabbb,baa,bab的操作进行说明。

1.基本操作

1.插入

1. 插入aaaa

首先插入串aaaa。对树中没有的节点进行新建，连接。结果：

对，就是这样的简单插入。（图中红色字母代表一个单词的结尾）

2. 插入abb

再插入串abb。在插入时，已有的节点直接走过去，没有的就插入再走过去。结果：

1.插入a

2.插入b

3.再插入b

完成。

3.插入aabbb

不再赘述，此操作请认真思考。结果：

4.插入baa

因为根节点的儿子中没有b，所以我们要在根节点后挂上一个b。其余的新建与第一个串一样。结果：

5.插入bab

与第二个串相同。结果：

结束。

2.查询

为了避免冗余，我们用简单的几张图片表示过程。以串aabbb为例：

完成。

简单的操作就是这些。但在实际应用中，往往不只是单纯返回一个串，更常用的是返回此处是否有串，或是串的个数，抑或状态。下面我们以几个题目做例子。

2.题目

1.洛谷P2580 于是他错误的点名开始了

大意：

给定\(n\)个字典串，再对\(m\)个模式串进行匹配，若匹配到，输出\(O\)，未匹配到，输出\(WRONG\)，若匹配到且之前已经被匹配，输出\(REPEAT\)。

解：真的是很基本的Trie树的题，此题在这里是做代码范例用途。详细解释见代码。（不要在意这神奇的代码风格）

#include <iostream>
#define re register
const int MAXN = 1000001;
struct Trie{                //定义Trie树的结构，因为当前节点后可能会有26个小写字母，也就是26个后继，所以数组开26大小。
    int next[26];
    bool exist, repeat;     //exist：是否是字符串结尾（当前位置是否有字符串）；repeat：此字符串是否被查询过。
}a[MAXN];
int top, n, m;
std::string str;
inline void Trie_insert() {
    int iter(0), now(0), tmp(0);        //iter：指向字符；now：指向节点。此两者起指针作用。
    for (iter; str[iter]; ++iter) {     //遍历当前插入字符串。
        tmp = str[iter] - 'a';          //将当前字母用数字表示。
        if(!a[now].next[tmp]) a[now].next[tmp] = ++top;     //如果当前节点没有代表该字母的后继，则新建节点。
        now = a[now].next[tmp];         //将指针向后移。
    }
    a[now].exist = true;                //当前节点代表字符串结尾。
    return ;
}
inline int Trie_search() {
    int iter(0), now(0), tmp(0);
    for (iter; str[iter]; ++iter) {     //遍历当前查询字符串。
        tmp = str[iter] - 'a';          //与上方操作相同。
        if(!a[now].next[tmp]) return 0; //如果当前节点没有代表该字母的后继，则说明查询失败，返回零。
        now = a[now].next[tmp];         //指针后移。
    }
    return a[now].exist ? (!a[now].repeat ? (a[now].repeat = 1) : 2) : 0;
  /*
        相当于：
        if(a[now].exist) {              //判断是否存在
            if(a[now].repeat) return 2; //判断是否查询过
            else {a[now].repeat = 1; return 1;}
        }
        else return 0;
  */
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (re int i = 1; i <= n; ++i) std::cin >> str, Trie_insert();
    std::cin >> m;
    for (re int i = 1; i <= m; ++i) {
        std::cin >> str;
        switch(Trie_search()) {     //得到查询的返回值。若是0，说明匹配未成功；是1，说明匹配成功；是2，说明匹配成功，且重复匹配。
            case (0): {
                std::cout << "WRONG\n";
                break;
            }
            case (1): {
                std::cout << "OK\n";
                break;
            }
            default: {
                std::cout << "REPEAT\n";
            }
        }
    }
    return 0;
}

就是这样。

2.洛谷P2922 [USACO08DEC] 秘密消息Secret Message

大意：

给定\(M(1 \leqslant M \leqslant 50000)\)个字典串，第\(i\)个字典串有\(Bi(1 \leqslant Bi \leqslant 10000)\)位。再给定N(\(1 \leqslant N \leqslant 50000\))个模式串，第\(i\)个模式串有\(Cj\)(\(1 \leqslant Cj \leqslant 10000\))位 (\((\sum_{i = 1}^{M}Bi + \sum_{j = 1}^{N}Cj) \leqslant 500000\))。对每个模式串\(j\)，求有多少串与当前模式串有相同前缀。(包括长度长于，等于与小于模式串的字典串)

解：在插入沿途做经过的标记，标记当前字母被几个字符串经过。在查询时\(ans\)加上经过字母上的结束标记。查询结束时，如果是走到字典串结尾而结束，\(ans\)加上结束标记，直接退出；如果是走到模式串结尾而结束，\(ans\)则不加结束标记，而是要加上经过标记，然后退出。

前面的加结束标记好理解，但为什么字典串比模式串长时要加经过标记呢？因为字典串比模式串长，说明字典串以模式串为前缀，按题意求有多少串与当前模式串有相同前缀，又因为经过标记正好代表这些串的个数，当然要用经过标记了。

这一道题思维量并不大，也算一道入门题。

#include <cctype>
#include <cstdio>
const int N = 10000;
struct Node{
    int next[2], exist, passby;         //exist：结束标记；passby：经过标记。
}cow[500010];
int m, n, b, j, tot, top;
bool fl(0);
char buf[N], *p = buf, *end = buf;
inline char Get_char() {
    if(p == end) {
        if(feof(stdin)) return (0);
        p = buf; end = buf + fread(buf, 1, N, stdin);
    }
    return *(p++);
}
inline void Get_int(int &x) {
    x = 0; char c(0);
    while (!isdigit(c = Get_char()));
    do {x = (x << 1) + (x << 3) + (c ^ 48);}
    while (isdigit(c = Get_char()));
    return ;
}
inline void Insert(int lent) {
    int now(0), c(0);
    for (int i = 1; i <= lent; ++i) {
        Get_int(c);
        if(!cow[now].next[c]) cow[now].next[c] = ++top;
        cow[cow[now].next[c]].passby++;         //普通插入，只不过多了经过标记。
        now = cow[now].next[c];
    }
    cow[now].exist++;
    return ;
}
inline void Query(int lent) {
    int now(0), c(0); tot = 0; fl = false; int i;
    for (i = 1; i <= lent; ++i) {
        Get_int(c);
        if(!cow[now].next[c]) {fl = true; break;}   //标记第一种情况，即字典串比模式串短。
        now = cow[now].next[c];
        tot += cow[now].exist;                      //加结束标记。
    }
    for (i = i + 1; i <= lent; ++i)
        Get_int(c);
    if(fl) {printf("%d\n", tot);}
    else {printf("%d\n", tot - cow[now].exist + cow[now].passby);}  //第二种情况，即字典串比模式串长，则减掉之前加上的结束标记，加上经过标记。
    return ;
}
int main() {
    Get_int(m); Get_int(n);             //不要在意快读。
    for (int i = 1; i <= m; ++i) {
        Get_int(b); Insert(b);          //插入操作。
    }
    for (int i = 1; i <= n; ++i) {
        Get_int(j); Query(j);           //查询操作。
    }
    return 0;
}

3.待添加

2.AC自动机