多模式字符串匹配 - AC自动机原理及实现

给一个字符串，找出字符串中指定的单词，如果是单个词，我们可以通过暴力解法，从头开始遍历字符串，判断是否存在指定的单词，当然还有一种更优的解法，那就是KMP算法，通过构造next数组，保存匹配的中间状态，在查找单词失败时，不用退回到字符串开头重新进行匹配，实现了O(m+n)的时间复杂度。这种在一个字符串中找一个单词的匹配成为单模式匹配，如果要在一个字符串中寻找多个子串了，那就是将要谈到的多模式匹配，如何实现呢？对每个子串进行KMP匹配，当然也可以。但是有一种更为优秀的多模式匹配算法，那就是AC自动机算法。

Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。

AC自动机算法可以理解为树形的KMP算法，不过不了解KMP也不影响学习AC自动机算法，不过需要了解字典树和多叉树的广度遍历算法。

Trie树，也叫字典树，是一种多叉树形数据结构，每个节点保存一个字符，一条路径上的所有节点保存一个字符串。以{"hers", "he", "his", "she"}构造的字典树为例：

如上图所示，每个单词在一条路径上，绿色节点表示该节点是一个单词的尾字符。其中root节点不存储任何字符。

看上面的图应该已经知道如何构造一个Trie树了，那代码如何实现呢？首先定义节点的结构体：

struct TrieNode {
    TrieNode*                           fail{nullptr}; // 失配指针
    std::vector                    exists;        // 该节点出是否存在完整单词
    std::unordered_map childs;        // 子节点，用 hash 表方便快速查询
};

其中：

exists字段用来存储以该节点字符结尾单词的长度，如单词"hers"，则该节点exists = {4}，用这个长度我们便可以截取出提取出字符串对应的该单词，而不用存储整个单词。

fail指针表示失配指针，后续将匹配过程会理解它。

childs用来存储子节点，为了快速定位子节点，我们用hash表存储子节点，键值为字符，value值为子节点其它信息

通过给定的多个单词构造Trie树代码如下：

TrieNode* buildTrie(const std::vector& words) {
    if (words.empty()) {
        cout << "[buildTrie] words is empty" << endl;
        return nullptr;
    }
    TrieNode* root = new TrieNode();
    for (auto& word : words) {
        TrieNode* tmp = root;
        for (char ch : word) {
            if (tmp->childs.find(ch) == tmp->childs.end()) {
                tmp->childs[ch] = new TrieNode();
            }
            tmp = tmp->childs[ch];
        }
        tmp->exists.emplace_back(word.size());
    }
    return root;
}

不要忘记在每个单词的尾字符节点存储单词的长度。

先看已构造好失配指针的图，后续讲如何构造失配指针

如图所示，每个节点的失配指针都指向指定节点，有的指向root节点，有的指向字符节点，那失配指针代表什么呢？可以理解为：
如果节点A的失配指针指向节点B，那么就表示：节点B结尾的字符串是节点A结尾的字符串的最长后缀：

• 节点[her]s.fail = s，s是该字典树中hers的最长后缀
• 节点[sh]e.fail = [h]e，he是该字典树中she的最长后缀
• 节点[h]e.fail = root，he在该字典树中没有最长后缀

可以自己体会一下

代码如下：

TrieNode* initAhoCorasick(const std::vector& words) {
    TrieNode* root = buildTrie(words);

    std::queue que;
    // 每个word的第一个字符的失配指针指向root节点
    for (auto& child : root->childs) {
        child.second->fail = root;
        que.emplace(child.second);
    }

    // 初始化失配指针，保存word字符串长度
    while (!que.empty()) {
        TrieNode* parNode = que.front();
        que.pop();
        for (auto& child : parNode->childs) {
            auto* subNode = child.second;
            auto* parFail = parNode->fail;
            while (parFail && (parFail->childs.find(child.first) == parFail->childs.end())) {
                parFail = parFail->fail;
            }
            if (parFail) {
                subNode->fail = parFail->childs[child.first];
            } else {
                subNode->fail = root;
            }
            if (!subNode->fail->exists.empty()) {
                subNode->exists.insert(
                    subNode->exists.end(), subNode->fail->exists.begin(), subNode->fail->exists.end());
            }
            que.emplace(subNode);
        }
    }
    return root;
}

root节点的子节点的失配指针都指向root，就是说每个单词的第一个字符都是不存在最长后缀的。

以字符串"ahishers"为例，去匹配之前生成的Trie树，找出字符串的单词。从头开始遍历字符串：

1. “a”：root没有为"a"的子节点，跳过，匹配下一个字符
2. “h”：root含有子节点"h"，继续遍历
3. “i”：“h"节点含有子节点"i”，继续
4. “s”：“i"含有子节点"s”，且存在一个单词"his"，继续
5. “h”：“s"不含子节点"h”，跳到"s"的失配节点，此"s"含有子节点"h"，继续
6. “e”：“h"含有子节点"e”，且存在单词"he, she"，继续
7. “r”：“e"不含没有为"r"的子节点，跳到失配节点"e”，此"e"节点含有子节点"r"，继续
8. “s”：“r"节点含有"s"子节点，存在单词"hers”，匹配结束

如此可找到字符串中的单词{"hers", "he", "his", "she"}

#include 
#include 
#include 
#include 
#include 
#include 

using std::cin, std::cout, std::endl;

struct TrieNode {
    TrieNode*                           fail{nullptr}; // 失配指针
    std::vector                    exists;        // 该节点出是否存在完整单词
    std::unordered_map childs;        // 子节点，用 hash 表方便快速查询
};

TrieNode* buildTrie(const std::vector& words) {
    if (words.empty()) {
        cout << "[buildTrie] words is empty" << endl;
        return nullptr;
    }
    TrieNode* root = new TrieNode();
    for (auto& word : words) {
        TrieNode* tmp = root;
        for (char ch : word) {
            if (tmp->childs.find(ch) == tmp->childs.end()) {
                tmp->childs[ch] = new TrieNode();
            }
            tmp = tmp->childs[ch];
        }
        tmp->exists.emplace_back(word.size());
    }
    return root;
}

TrieNode* initAhoCorasick(const std::vector& words) {
    TrieNode* root = buildTrie(words);

    std::queue que;
    // 每个word的第一个字符的失配指针指向root节点
    for (auto& child : root->childs) {
        child.second->fail = root;
        que.emplace(child.second);
    }

    // 初始化失配指针，保存word字符串长度
    while (!que.empty()) {
        TrieNode* parNode = que.front();
        que.pop();
        for (auto& child : parNode->childs) {
            auto* subNode = child.second;
            auto* parFail = parNode->fail;
            while (parFail && (parFail->childs.find(child.first) == parFail->childs.end())) {
                parFail = parFail->fail;
            }
            if (parFail) {
                subNode->fail = parFail->childs[child.first];
            } else {
                subNode->fail = root;
            }
            if (!subNode->fail->exists.empty()) {
                subNode->exists.insert(
                    subNode->exists.end(), subNode->fail->exists.begin(), subNode->fail->exists.end());
            }
            que.emplace(subNode);
        }
    }
    return root;
}

std::vector acQuery(const std::vector& words, const std::string& text) {
    if (text.empty()) {
        cout << "[acQuery] text is empty" << endl;
        return {};
    }
    TrieNode* root = initAhoCorasick(words);
    if (root == nullptr) {
        cout << "[acQuery] initAhoCorasick() failed" << endl;
        return {};
    }

    std::vector hitWords;
    for (size_t i = 0; i < text.size(); ++i) {
        while ((root->childs.find(text[i]) == root->childs.end()) && root->fail) {
            root = root->fail;
        }
        if (root->childs.find(text[i]) != root->childs.end()) {
            root = root->childs[text[i]];
            for (int len : root->exists) {
                hitWords.emplace_back(text.substr(i - len + 1, len));
            }
        }
    }
    return hitWords;
}

int main() {
    std::vector words{"hers", "he", "his", "she"};
    std::string              text{"ahishers"};

    auto&& hitWords = acQuery(words, text);
    std::copy(hitWords.begin(), hitWords.end(), std::ostream_iterator{cout, "n"});

    return EXIT_SUCCESS;
}

// clang++ -std=c++17 ac.cc
// ./a.out