AC自动机模板：O(n)多模式匹配实战指南

AC自动机（Aho-Corasick Automaton），也被称为后缀树或多模式自动机，是一种高效的数据结构，用于在文本中查找多个模式串。它由Alfred Aho、Jeffrey Corasick和Vojtech Ullman在1975年的贝尔实验室提出，被广泛应用于编译器设计、全文搜索引擎和编程竞赛等领域，特别是在ACM（美国计算机协会）和OI（奥林匹克信息学竞赛）等高级算法比赛中。 AC自动机的核心数据结构是一个有向图，其中每个节点代表一个前缀，边连接具有公共后缀的节点。这个图的构建过程中，首先初始化一个大小为`maxd`的数组`ch`，表示每个字符到其可能子节点的映射。同时，还有两个辅助数组`f`和`val`分别存储失败链接和模式值。 1. 初始化： - 函数`init()`将所有字符映射表清零，并设置根节点的大小为1。 - `id(char c)`函数用来获取字符c的ASCII码减去'a'后的索引。 2. 插入模式： - 函数`insert(const char *s, int v)`接受一个模式串`s`和一个整数值`v`，通过遍历模式串并扩展图结构，为每个新遇到的字符分配新的节点，并更新节点的值（表示匹配次数）。 3. 查找模式： - `find(const char *s)`遍历输入字符串`s`，根据`f`数组计算每个节点的最长公共前缀，累计值为所有匹配模式的总和。 4. 计算失败链接： - `getfail()`是关键步骤，用于构建失败链接表`f`，使得对于每个节点，如果它的某个子节点可以到达，则失败链接指向那个子节点。通过广度优先搜索（BFS）策略，从所有单个字符节点开始，逐渐扩展到整个图。 这些操作的时间复杂度是线性的，即`O(n)`，n为输入字符串的长度，这使得AC自动机成为处理多模式匹配问题的理想选择。在ACM/OI竞赛中，模板函数如上述代码所示，可以极大地提高解题效率，特别是在需要处理大量模式或者频繁匹配的情况下。 使用此模板，参赛者可以直接调用`init()`、`insert()`和`find()`来处理题目中的模式匹配需求，而`getfail()`则通常在首次构建图之后执行一次。理解并掌握AC自动机的工作原理和代码实现，将有助于你在算法竞赛中快速解决涉及模式匹配的问题，从而提升解题能力。