AC自动机学习笔记

AC自动机有两个前置知识点,KMP算法和字典树

KMP算法:

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris于1977年共同发明。KMP算法的核心思想是当字符串不匹配时，能够利用已经部分匹配的信息，避免从头开始匹配，从而提高匹配效率。

KMP算法的工作原理

KMP算法的关键在于构建一个部分匹配表（Partial Match Table，也称为前缀函数或失败函数），该表用于在不匹配的情况下决定下一步的匹配位置。

部分匹配表（Partial Match Table）

部分匹配表是一个数组，对于模式字符串（Pattern）中的每个位置，它记录了该位置之前的子字符串中，前缀和后缀的最长公共元素长度。例如，对于字符串"ABCDABD"，部分匹配表如下：

A B C D A B D
0 0 0 0 1 2 0

在这个例子中，"ABCDABD"的前缀"AB"和后缀"AB"是最长的公共元素，长度为2。

匹配过程

初始化：从模式字符串的第一个字符开始，与文本字符串的第一个字符进行比较。
匹配：如果字符匹配，移动到下一个字符继续比较。
不匹配：如果字符不匹配，查看部分匹配表，找到当前位置的前缀和后缀的最长公共元素长度，然后将模式字符串滑动到该长度的位置，继续与文本字符串的当前字符比较。
重复：重复步骤2和3，直到模式字符串的所有字符都匹配完成，或者文本字符串结束。

KMP算法的优势

效率：KMP算法的时间复杂度是O(n+m)，其中n是文本字符串的长度，m是模式字符串的长度。这比朴素的字符串匹配算法（时间复杂度为O(n*m)）要高效得多。
无需回溯：在不匹配的情况下，KMP算法不需要将模式字符串完全回溯到开始位置，而是根据部分匹配表直接跳到下一个可能的匹配位置。

KMP算法的应用

KMP算法广泛应用于各种需要字符串匹配的场景，如文本搜索、数据压缩、模式识别等。

示例:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 计算部分匹配表 (Partial Match Table)
vector<int> computeLPSArray(const string &pattern) {
    int len = 0; // length of the previous longest prefix suffix
    int i = 1;
    vector<int> lps(pattern.size(), 0);
    
    while (i < pattern.size()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP算法主函数
void KMPSearch(const string &text, const string &pattern) {
    if (pattern.empty()) return;

    vector<int> lps = computeLPSArray(pattern);
    int i = 0; // index for text
    int j = 0; // index for pattern

    while (i < text.size()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == pattern.size()) {
            cout << "Pattern found at index " << i - j << endl;
            j = lps[j - 1];
        } else if (i < text.size() && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i = i + 1;
            }
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}

BM算法

注意:BM算法会再一定情况下复杂度退化到\(O(nm)\),故算法竞赛中不常用BM算法
BM（Boyer-Moore）算法是一种用于字符串搜索的高效算法，由Robert S. Boyer和J Strother Moore在1977年提出。它在许多文本编辑器和字符串处理程序中被用作标准字符串搜索算法。BM算法的核心思想是从右到左（而不是像KMP算法那样从左到右）检查模式字符串，并利用两个规则——坏字符规则和好后缀规则——来跳过不匹配的字符，从而减少比较次数。

坏字符规则（Bad Character Rule）

坏字符规则指出，当在文本中搜索模式字符串时，如果发现一个不匹配的字符（坏字符），则可以利用模式字符串中该字符之前的所有匹配字符来确定下一步的搜索位置。具体来说，算法查找模式字符串中所有与坏字符相同的字符，并计算出最右边的一个。然后，将模式字符串滑动到该字符的下一个位置，并从该位置开始重新进行匹配。

好后缀规则（Good Suffix Rule）

好后缀规则适用于当模式字符串的尾部与文本中的一个子字符串完全匹配，但整个模式字符串与文本不匹配的情况。在这种情况下，算法将模式字符串滑动到好后缀的下一个位置，并从好后缀的末尾开始重新匹配。

BM算法的工作原理

初始化：从文本字符串的开始位置和模式字符串的末尾位置开始比较。
比较：从右到左比较模式字符串和文本字符串的字符。
坏字符：如果在比较过程中遇到坏字符，应用坏字符规则来确定新的搜索位置。
好后缀：如果模式字符串的尾部与文本中的一个子字符串完全匹配，但整个模式字符串不匹配，应用好后缀规则来确定新的搜索位置。
重复：重复步骤2-4，直到找到匹配的子字符串或到达文本字符串的末尾。

BM算法的优势

效率：BM算法在最佳情况下可以达到O(n/m)的时间复杂度，其中n是文本字符串的长度，m是模式字符串的长度。在最坏情况下，时间复杂度为O(nm)。
跳过匹配：BM算法通过跳过已知不匹配的字符，减少了不必要的字符比较。

BM算法的应用

BM算法适用于在大型文本中搜索短字符串的场景，如文本编辑器中的查找功能、数据压缩、生物信息学中的序列比对等。

字典树

字典树（Trie），也被称为前缀树或单词查找树，是一种用于存储字符串集合的树形数据结构。它能够高效地进行字符串的查找、插入和删除操作，特别适用于处理具有共同前缀的字符串集合。字典树的主要特点是将字符串的每个字符作为节点，并将字符串的前缀共享，从而减少存储空间和提高搜索效率。

字典树的结构

字典树的每个节点通常包含以下信息：

一个字符：表示从根节点到当前节点的路径上的字符。
一个布尔值：通常用来标记当前节点是否代表一个完整的单词的结尾。
一个子节点数组：包含子节点的指针，每个子节点对应一个字符。

根节点不包含任何字符，它指向一个或多个子节点，每个子节点代表一个字符串的第一个字符。从根节点开始，沿着特定的路径可以找到所有的字符串。

字典树的特点

空间优化：由于共同前缀的共享，字典树可以有效地减少存储空间，尤其是当字符串集合中有很多共同前缀时。
搜索效率：在最佳情况下，搜索一个字符串的时间复杂度是O(m)，其中m是字符串的长度。这是因为搜索过程中不需要回溯，每一步都是基于字符的匹配。
动态更新：字典树可以动态地插入和删除字符串，而不需要重新构建整个数据结构。

字典树的应用

自动补全：在文本编辑器或搜索引擎中提供单词自动补全功能。
拼写检查：检查用户输入的单词是否拼写正确。
IP路由：在路由器中用于IP地址的查找。
词频统计：统计文本中单词出现的频率。

字典树的实现

字典树的实现通常涉及以下几个步骤：

节点定义：

int tire[3000005][62];
int cnt[3000005];
int idx;

int get_num(char c){
    if(c>='a'&&c<='z')return c-'a'+26;
    else if(c>='A'&&c<='Z')return c-'A';
    return c-'0'+52;
}

插入操作：从根节点开始，根据字符串的每个字符遍历或创建子节点，直到字符串的末尾。在最后一个字符的节点上设置布尔标记为true，表示单词的结束。

void insert(string& str){
    int p{0};
    for(int i{0};i<str.size();i++){
        int j=get_num(str[i]);
        if(!tire[p][j])tire[p][j]=++idx;
        p=tire[p][j];
        cnt[p]++;//对每一个字符到达的节点都标记，这样可以查前缀，只标记结尾时只能查整串
    }
}

搜索操作：从根节点开始，根据要搜索的字符串的每个字符遍历子节点。如果能够遍历到字符串的末尾，并且最后一个节点的布尔标记为true，则表示找到了匹配的单词。

int query(string& str){
    int p{0};
    for(int i{0};i<str.size();i++){
        int j=get_num(str[i]);
        if(!tire[p][j])return 0;
        p=tire[p][j];
    }
    return cnt[p];
}

删除操作：删除操作相对复杂，需要从根节点开始，根据字符串的每个字符遍历子节点，并适当地删除子节点。如果一个节点在删除后没有子节点且不是必须的前缀，则可以删除该节点。

标签：字符,AC,匹配,笔记,算法,KMP,字符串,自动机,节点
From： https://www.cnblogs.com/manjuan/p/18086400