KMP（Knuth-Morris-Pratt）算法是一种用于在字符串中查找模式的高效算法。其核心思想是通过利用已匹配部分的信息来避免不必要的比较，从而提高匹配效率。以下是 KMP 算法的详细原理和步骤：

KMP 算法原理：

1. 构建 KMP 表（部分匹配表）： 在模式字符串中，对于每个位置，计算它之前的子串的最长相同前缀和后缀的长度。这个信息被存储在一个表中，称为部分匹配表（partial match table）或 KMP 表。

2. 使用 KMP 表进行匹配： 在文本中逐一匹配字符时，当发现不匹配时，通过查看 KMP 表中的值，决定模式字符串应该向右移动多少位，从而避免重复的比较。

KMP 算法步骤：

步骤 1：构建 KMP 表

对于模式字符串 pattern，我们要构建一个长度为 m 的部分匹配表 table。其中 table[i] 表示模式字符串的前缀子串 pattern[0:i] 的最长相同前缀和后缀的长度。

cpp
vector<int> build_kmp_table(const string& pattern) {
    int m = pattern.length();
    vector<int> table(m, 0);
    int j = 0;

    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = table[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            ++j;
        }

        table[i] = j;
    }

    return table;
}

步骤 2：使用 KMP 表进行匹配

在文本字符串 text 中搜索模式字符串 pattern。

cpp
vector<int> kmp_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> matches;
    
    if (m == 0) {
        for (int i = 0; i < n; ++i) {
            matches.push_back(i);
        }
        return matches;
    }

    vector<int> table = build_kmp_table(pattern);
    int j = 0;

    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = table[j - 1];
        }

        if (text[i] == pattern[j]) {
            ++j;
        }

        if (j == m) {
            matches.push_back(i - m + 1);
            j = table[j - 1];
        }
    }

    return matches;
}

KMP 算法示例：

考虑文本字符串 text = "ABABDABACDABABCABAB" 和模式字符串 pattern = "ABABCABAB"。

1. 构建 KMP 表：

   plaintext
   pattern:  ABABCABAB
   table:    001201214
   

2. 使用 KMP 表进行匹配：

   plaintext
   text:           ABABDABACDABABCABAB
   pattern match:          ABABCABAB
   indices:                      10
   

在上面的示例中，KMP 算法通过构建 KMP 表，避免了不必要的字符比较，找到了模式字符串在文本中的匹配位置。

cpp
#include <iostream>
#include <vector>

using namespace std;

// 构建 KMP 表
vector<int> build_kmp_table(const string& pattern) {
    int m = pattern.length();
    vector<int> table(m, 0);  // 初始化部分匹配表，初始值都为 0
    int j = 0;  // j 用于记录前缀的长度

    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            // 如果当前字符不匹配，回溯到前一个字符的部分匹配长度位置
            j = table[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            // 如果当前字符匹配，更新部分匹配长度
            ++j;
        }

        table[i] = j;  // 将当前位置的部分匹配长度记录到部分匹配表中
    }

    return table;
}

// KMP 搜索
vector<int> kmp_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> matches;
    
    if (m == 0) {
        // 特殊情况：模式串为空，匹配所有位置
        for (int i = 0; i < n; ++i) {
            matches.push_back(i);
        }
        return matches;
    }

    vector<int> table = build_kmp_table(pattern);
    int j = 0;  // j 用于记录已匹配的长度

    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            // 如果当前字符不匹配，回溯到前一个字符的部分匹配长度位置
            j = table[j - 1];
        }

        if (text[i] == pattern[j]) {
            // 如果当前字符匹配，更新已匹配的长度
            ++j;
        }

        if (j == m) {
            // 如果已匹配的长度等于模式串长度，表示找到了匹配位置
            matches.push_back(i - m + 1);
            j = table[j - 1];  // 回溯到前一个字符的部分匹配长度位置，继续搜索下一个匹配
        }
    }

    return matches;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    
    vector<int> result = kmp_search(text, pattern);

    if (!result.empty()) {
        cout << "Pattern found at positions: ";
        for (int pos : result) {
            cout << pos << " ";
        }
        cout << endl;
    } else {
        cout << "Pattern not found in the text." << endl;
    }

    return 0;
}