Knuth-Morris-Pratt

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串搜索算法，用于在一个主串（text）中查找一个模式串（pattern）的匹配。KMP算法的核心在于预处理模式串，生成一个部分匹配表（也称为"前缀函数"或"部分失败函数"），这个表用于在搜索过程中遇到不匹配的情况时，能够快速确定下一步的搜索位置，从而避免了从主串的开头重新开始搜索。

KMP算法的关键步骤

1. 预处理模式串：生成部分匹配表 π，π[i] 表示模式串从位置 0 到 i 的最长的相同前缀和后缀的长度。
2. 搜索过程：使用部分匹配表来确定在搜索过程中遇到不匹配字符时，模式串应该向右移动多远。

部分匹配表的构建

构建部分匹配表 π 的步骤如下：

1. 初始化 π[0] = 0。
2. 对于 i 从 1 到 m-1（模式串的长度减1）：
   • 如果 pattern[i-1] 等于 pattern[π[i-1]]，则 π[i] = π[i-1] + 1。
   • 否则，设置 j = π[i-1]。
   • 循环直到找到 j > 0 且 pattern[j-1] \neq pattern[i-1] 或者 j == 0。
   • 如果 pattern[j-1] == pattern[i]，则 π[i] = j。
   • 否则，π[i] = 0。

KMP搜索算法

1. 初始化两个指针 i = 0（主串的当前位置）和 j = 0（模式串的当前位置）。
2. 当 i < n（主串的长度）且 j < m（模式串的长度）时：
   • 如果 text[i] == pattern[j]，则 i 和 j 都加1。
   • 如果 j == m，则找到一个匹配，记录匹配的开始位置，然后设置 j = π[j-1] 继续搜索下一个匹配。
   • 如果 text[i] \neq pattern[j] 且 j > 0，则设置 j = π[j-1]。
   • 如果 j == 0，则 i 加1。

KMP算法的示例代码（以C++为例）

#include <iostream>
#include <vector>
using namespace std;

// 构建部分匹配表
vector<int> computePartialMatchTable(const string& pattern) {
   
    int m = pattern.size();
    vector<int> π(m, 0);
    for (int i = 1; i < m; ++i) {
   
        int j = π[i - 1];
        while (j > 0 && pattern[i - 1] != pattern[j - 1]) {
   
            j = π[j - 1];
        }
        if (pattern[i - 1] == pattern[j - 1]) {
   
            π[i] = j + 1;
        }
    }
    return π;
}

// KMP搜索算法
void KMP(const string& text, const string& pattern) {
   
    int n = text.size();
    int m = pattern.size();
    if (m == 0 || n == 0 || m > n) return;

    vector<int> π = computePartialMatchTable(pattern);
    int i = 0, j = 0;

    while (i < n) {
   
        if (pattern[j] == text[i]) {
   
            i++;
            j++;
        }
        if (j == m) {
   
            cout << "匹配位置：" << i - j << endl;
            j = π[j - 1];
        }
        else if (i < n && pattern[j] != text[i]) {
   
            if (j != 0) {
   
                j = π[j - 1];
            } else {
   
                i++;
            }
        }
    }
}

// 测试代码
int main() {
   
    string text = "ABC ABCDAB ABCDABCDABDE";
    string pattern = "ABCDABD";
    KMP(text, pattern);
    return 0;
}

注意事项

• KMP算法的时间复杂度为 O(n + m)，其中 n 是主串的长度，m 是模式串的长度。
• 构建部分匹配表是 KMP 算法的关键步骤，它决定了搜索过程中的效率。