算法009-AC自动机

AC自动机

KMP 适合用一个模式串匹配一个母串。如果有大量模式串，分别执行 KMP，就需要反复扫描母串。

先把所有模式串建立成 Trie，再给 Trie 增加 fail 指针，最后只扫描一次母串。

因此可以简单理解为：AC 自动机 = Trie + KMP 的失配思想

Trie比较简单，这里主要说一下，fail指针的核心。

fail 需要通过 BFS 构建，因为一个节点的 fail 依赖其父节点的 fail，所以必须先处理浅层节点，再处理深层节点。根节点第一层孩子的 fail 都指向根节点。对于一条真实的 Trie 边 current --c--> child，孩子节点的 fail 可以写为：

node[child].fail = node[node[current].fail].next[c];

这句话的含义是，先让父节点 current 走到自己的 fail 状态，再从该状态读取字符 c，最终到达的位置就是 child 的 fail。例如 abcdef 的父节点是 abcde，如果 fail(abcde) 指向 bcde，而 bcde 再读取字符 f 可以到达 bcdef，那么 fail(abcdef) 就指向 bcdef。

构建过程中还需要补全不存在的字符转移。如果当前节点没有字符 c 的真实 Trie 子节点，就执行：

node[current].next[c] = node[node[current].fail].next[c];

这表示当前状态不能读取字符 c 时，直接使用其 fail 状态读取字符 c 的结果。通过这种方式，可以把原本需要不断沿 fail 跳转的过程提前计算出来。完成补全后，搜索母串时每读取一个字符，只需要执行一次 state = node[state].next[c]。

作为子字符串出现在单词中的字符串数目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串是字符串中的一个连续字符序列。

示例 1：

输入：patterns = ["a","abc","bc","d"], word = "abc"
输出：3
解释：

"a" 是 "abc" 的子字符串。
"abc" 是 "abc" 的子字符串。
"bc" 是 "abc" 的子字符串。
"d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = ["a","b","c"], word = "aaaaabbbbb"
输出：2
解释：

"a" 是 "aaaaabbbbb" 的子字符串。
"b" 是 "aaaaabbbbb" 的子字符串。
"c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = ["a","a","a"], word = "ab"
输出：3
解释：
patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。

提示： 1 <= patterns.length <= 100 > 1 <= patterns[i].length <= 100 > 1 <= word.length <= 100 > patterns[i] 和 word 由小写英文字母组成

思路

暴力肯定可以的，但是这里选择AC自动机。

本题要求统计 patterns 中有多少个字符串是 word 的子串，而不是统计这些字符串总共出现了多少次。例如 patterns = c，word = "aaaaabbbbb"，答案应该是 2，而不是 10。因此模式串第一次被匹配后，需要将对应节点标记为已经统计。这里使用 cnt = 0 直接置零，当然也可以设置标志位。

搜索时，当前状态本身和它的 fail 链上都可能存在模式串。例如模式串中同时存在 he 和 she，扫描到 she 节点时，she 匹配成功，而它的 fail 指向 he，所以 he 也同时匹配成功。因此搜索到一个状态后，需要继续沿 fail 链寻找模式串结尾节点。

代码

struct Node {
    int next[26]{};
    int fail{};
    int cnt{};
};

class AC {
public:
    vector<Node> node;

    AC(){
        node.emplace_back();
    }

    void insert(const string& s) {
        int root = 0;
        for (char c : s) {
            if (node[root].next[c - 'a'] == 0) {
                node[root].next[c - 'a'] = node.size();
                node.emplace_back();
            }
            root = node[root].next[c - 'a'];
        }
        node[root].cnt++;
    }

    void build() {
        queue<int> q;

        for (int c = 0; c < 26; c++) {
            int child = node[0].next[c];
            if (child != 0) {
                q.push(child);
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int c = 0; c < 26; c++) {
                int child = node[current].next[c];
                if (child != 0) {
                    node[child].fail = node[node[current].fail].next[c];
                    q.push(child);
                } else {
                    node[current].next[c] = node[node[current].fail].next[c];
                }
            }
        }
    }

    long long search(const string& s) {
        int root = 0;
        long long ans = 0;

        for (char c : s) {
            root = node[root].next[c - 'a'];
            int current = root;
            while (current != 0) {
                ans += node[current].cnt;
                node[current].cnt = 0;
                current = node[current].fail;
            }
        }

        return ans;
    }
};


class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        AC ac{};
        for (auto & p : patterns) {
            ac.insert(p);
        }

        ac.build();

        return ac.search(word);
    }
};

该算法还有一定优化空间，但主要目的是AC自动机的核心思想。