前缀表与KMP算法

KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的高效算法，它能够在文本串中查找模式串出现的位置。KMP算法的核心在于避免重复比较字符，从而提高匹配效率。

KMP算法的基本思路

预处理模式串：通过构建一个“部分匹配表”（或称为“失配表”），在模式串中记录每个位置的最长可匹配前缀长度。
匹配过程：利用部分匹配表，在匹配失败时，根据前缀信息跳过不必要的比较，从而加速匹配过程。

部分匹配表（LPS数组）

LPS（Longest Prefix Suffix）数组用于存储模式串的每个前缀的最长相等前后缀的长度。具体构建方式如下：

**LPS[i]**：表示模式串的前缀（pattern[0] 到 pattern[i]）的最长相等前后缀的长度。

KMP算法实现

下面是KMP算法的完整实现，包括LPS数组的构建和匹配过程：

cpp

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

// 函数用于构建LPS数组
vector<int> computeLPS(const string& pattern) {
    int m = pattern.size();
    vector<int> lps(m);
    int length = 0; // 上一个最长前缀后缀的长度
    lps[0] = 0;     // LPS[0]始终为0

    for (int i = 1; i < m; i++) {
        while (length > 0 && pattern[i] != pattern[length]) {
            length = lps[length - 1]; // 回溯
        }
        if (pattern[i] == pattern[length]) {
            length++;
        }
        lps[i] = length;
    }
    return lps;
}

// KMP搜索算法
vector<int> KMPSearch(const string& text, const string& pattern) {
    vector<int> lps = computeLPS(pattern);
    vector<int> positions; // 存储匹配的起始位置

    int n = text.size();
    int m = pattern.size();
    int i = 0; // 文本指针
    int j = 0; // 模式指针

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == m) { // 找到匹配
            positions.push_back(i - j);
            j = lps[j - 1]; // 继续查找下一个匹配
        } else if (i < n && pattern[j] != text[i]) { // 匹配失败
            if (j != 0) {
                j = lps[j - 1]; // 根据LPS表跳转
            } else {
                i++; // 否则向前移动文本指针
            }
        }
    }
    return positions;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";

    vector<int> result = KMPSearch(text, pattern);
    for (int pos : result) {
        cout << "Pattern found at index: " << pos << endl;
    }
    return 0;
}

代码解析

computeLPS函数：构建LPS数组，遍历模式串并填充LPS数组，使用回溯逻辑。
KMPSearch函数：使用LPS数组进行模式匹配：
- 使用两个指针 i 和 j 分别指向文本和模式串。
- 如果字符匹配，两个指针同时移动。
- 如果模式串匹配完成，将起始位置保存。
- 如果不匹配，根据LPS数组调整模式指针。

复杂度分析

时间复杂度：O(n + m)，其中 n 是文本串的长度，m 是模式串的长度。
空间复杂度：O(m)，用于存储LPS数组。

KMP算法是一个非常高效的字符串匹配算法，适用于大规模文本搜索。希望这个解释和示例代码对你理解KMP算法有帮助！如果你有任何问题或需要进一步的解释，请告诉我！

当然可以！让我们通过一个具体的实例来演示KMP算法的工作过程。

示例

假设我们有以下文本串和模式串：

文本串：text = "ABABDABACDABABCABAB"
模式串：pattern = "ABABCABAB"

我们要找到模式串在文本串中的所有出现位置。

步骤 1：构建LPS数组

首先，我们需要构建模式串的LPS数组。

模式串：`ABABCABAB`

计算LPS数组：
- lps[0] = 0（第一个字符没有前缀和后缀）
- lps[1] = 0（A没有相等的前后缀）
- lps[2] = 1（AB的前缀A和后缀A相等）
- lps[3] = 2（ABA的前缀AB和后缀AB相等）
- lps[4] = 0（ABAB没有相等的前后缀）
- lps[5] = 1（ABABC的前缀A和后缀A相等）
- lps[6] = 2（ABABCA的前缀AB和后缀AB相等）
- lps[7] = 3（ABABCAB的前缀ABA和后缀ABA相等）
- lps[8] = 4（ABABCABA的前缀ABAB和后缀ABAB相等）

最终的LPS数组为：

plaintext

1	lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]

步骤 2：进行KMP搜索

接下来我们使用KMP算法进行匹配。

初始化：
- i = 0（文本指针）
- j = 0（模式指针）
- positions = []（存储匹配位置）
开始匹配：
- 第 1 次比较：text[0] = 'A', pattern[0] = 'A' → 匹配，i++, j++ → i = 1, j = 1
- 第 2 次比较：text[1] = 'B', pattern[1] = 'B' → 匹配，i++, j++ → i = 2, j = 2
- 第 3 次比较：text[2] = 'A', pattern[2] = 'A' → 匹配，i++, j++ → i = 3, j = 3
- 第 4 次比较：text[3] = 'B', pattern[3] = 'B' → 匹配，i++, j++ → i = 4, j = 4
- 第 5 次比较：text[4] = 'D', pattern[4] = 'C' → 不匹配。根据LPS数组，j = lps[3] = 2，回溯到pattern[2]。
- 继续比较：text[4] = 'D', pattern[2] = 'A' → 不匹配，j = lps[1] = 0，重置j。i++ → i = 5。
继续匹配：
- 第 6 次比较：text[5] = 'A', pattern[0] = 'A' → 匹配，i++, j++ → i = 6, j = 1
- 第 7 次比较：text[6] = 'B', pattern[1] = 'B' → 匹配，i++, j++ → i = 7, j = 2
- 第 8 次比较：text[7] = 'A', pattern[2] = 'A' → 匹配，i++, j++ → i = 8, j = 3
- 第 9 次比较：text[8] = 'C', pattern[3] = 'B' → 不匹配。根据LPS，j = lps[2] = 1，回溯到pattern[1]。
- 继续比较：text[8] = 'C', pattern[1] = 'B' → 不匹配，j = lps[0] = 0，重置j。i++ → i = 9。
再次匹配：
- 第 10 次比较：text[9] = 'D', pattern[0] = 'A' → 不匹配，i++ → i = 10。
- 第 11 次比较：text[10] = 'A', pattern[0] = 'A' → 匹配，i++, j++ → i = 11, j = 1
- 第 12 次比较：text[11] = 'B', pattern[1] = 'B' → 匹配，i++, j++ → i = 12, j = 2
- 第 13 次比较：text[12] = 'C', pattern[2] = 'A' → 不匹配，j = lps[1] = 0，重置j。i++ → i = 13。
- 第 14 次比较：text[13] = 'A', pattern[0] = 'A' → 匹配，i++, j++ → i = 14, j = 1
- 第 15 次比较：text[14] = 'B', pattern[1] = 'B' → 匹配，i++, j++ → i = 15, j = 2
- 第 16 次比较：text[15] = 'A', pattern[2] = 'A' → 匹配，i++, j++ → i = 16, j = 3
- 第 17 次比较：text[16] = 'B', pattern[3] = 'B' → 匹配，i++, j++ → i = 17, j = 4
- 第 18 次比较：text[17] = 'C', pattern[4] = 'C' → 匹配，i++, j++ → i = 18, j = 5
- 第 19 次比较：text[18] = 'A', pattern[5] = 'A' → 匹配，i++, j++ → i = 19, j = 6
- 第 20 次比较：text[19] = 'B', pattern[6] = 'B' → 匹配，i++, j++ → i = 20, j = 7
- 第 21 次比较：i = 20，超出文本长度，停止匹配。

匹配结果

在整个过程中，我们找到了模式串在文本串中的匹配起始位置：

匹配位置：positions = [10]

总结

模式串 "ABABCABAB" 在文本串 "ABABDABACDABABCABAB" 中的匹配位置是 10。

这种通过LPS数组的预处理，使得算法能够避免重复比较，提高了效率，特别是在文本较长和模式较短的情况下尤为明显。如果你有其他问题或需要更深入的解释，请随时问我！