KMP算法

KMP 算法（Knuth-Morris-Pratt Algorithm） 是计算机科学中一种极其高效的字符串匹配算法。

它的核心威力在于：当字符串匹配发生“失配”时，它不回溯主串的指针，而是利用已经匹配过的部分信息，将模式串（Pattern）尽可能多地向右滑动。

一. 背景：为什么需要 KMP？

假设我们要在主串 S 中查找模式串 P。

1.1 暴力匹配法

如果不使用技巧，我们的做法是：

S[0] 和 P[0] 对比，如果一样，比下一个；如果不一样，S 指针回溯到 1，P 指针回溯到 0，重新开始。
痛点：S 指针会不断回退。
效率：最坏时间复杂度为。

1.2 KMP 的改进

KMP 算法极其聪明，它发现：在刚刚匹配过的部分中，其实蕴含了大量信息。我们不需要把 S 指针回退，只需要把 P 串向右滑动到“合适”的位置即可。
时间复杂度：（N 是主串长度，M 是模式串长度）。

二. 核心概念：前缀、后缀与最长公共长度

要理解 KMP，必须先理解三个概念，这是 KMP 的灵魂。

以字符串 "ABABCA" 为例：

前缀 (Prefix)：必须包含第一个字符，不包含最后一个字符的子串。
- A, AB, ABA, ABAB, ABABC
后缀 (Suffix)：必须包含最后一个字符，不包含第一个字符的子串。
- A, CA, BCA, ABCA, BABCA
最长公共前后缀长度 (LPS - Longest Proper Prefix which is also a Suffix)：
- 在当前字符串中，前缀集合和后缀集合中相同的、且长度最长的那个子串的长度。

举例计算 LPS（这对理解 Next 数组至关重要）：

模式串子串 (P)	前缀集合	后缀集合	最长公共前后缀 (LPS)	LPS长度
A	无	无	无	0
AB	A	B	无	0
ABA	A, AB	A, BA	A	1
ABAB	A, AB, ABA	B, AB, BAB	AB	2
ABABC	…	…	无	0
ABABCA	…	…	A	1

三. KMP 的核心：Next 数组

Next 数组（有些教材称为 PMT 表）本质上就是存储了模式串中每一个位置对应的 LPS 长度。

它的作用是告诉程序：“当你在第 j 位匹配失败时，你应该跳到模式串的哪个位置重新匹配，而不需要移动主串指针。”

3.1 为什么 LPS 能帮我们跳跃？

假设我们要匹配：

主串 Text: ...A B A B A B Z...
模式 Pattern: A B A B A B C
索引 Index: 0 1 2 3 4 5 6

过程分析：

我们一直匹配到了 Index 5 (B)，都相等。
到了 Index 6，主串是 Z，模式串是 C。失配！
观察：在失配字符 C 之前，我们已经成功匹配了子串 ABABAB。
查表：ABABAB 的最长公共前后缀是 ABAB，长度为 4。
行动：这意味头部 4 个字符 ABAB 和尾部 4 个字符 ABAB 是一样的。既然尾部已经和主串匹配过了，那头部的 ABAB 肯定也匹配主串！
结果：我们不需要回退主串，直接把模式串向右滑动，让模式串的第 4 号元素（下标为 4，即第 5 个字符）对准主串当前位置即可。

四.示例

场景设定

主串 (Text)：A B A B A B C (索引 0-6)
模式串 (Pattern)：A B A B C (索引 0-4)

我们的目标是：用 A B A B C 去匹配 A B A B A B C。

第一阶段：准备工作（构建 Next 数组）

在匹配之前，模式串先“自我体检”，算出 Next 数组。模式串：A B A B C

A (前缀无)：Next[0] = 0
AB (前缀A, 后缀B, 不等):Next[1] = 0
ABA (前缀A, 后缀A, 相等): Next[2] = 1
ABAB (前缀AB, 后缀AB, 相等): Next[3] = 2
ABABC (前缀AB, 后缀BC, 不等): Next[4] = 0

最终 Next 数组：[0, 0, 1, 2, 0]

关键点：注意索引 3 的位置是 2。这意味着如果你在 j=4 (字符 ‘C’) 处匹配失败了，你可以回退到 j=2 (字符 ‘A’) 继续试，因为前面的 AB 是已经确定的。

第二阶段：匹配过程

现在开始跑你的 C++ kmpSearch 函数。 i 指向主串，j 指向模式串。

步骤 1：顺利的开始

i 和 j 一起跑，直到遇到不一样的地方。

状态：
- 主串：A B A B A B C
- 模式：A B A B C
- 匹配：Text[0..3] 和 Pattern[0..3] 全部匹配。
- 此时：i = 4, j = 4。

步骤 2：发生冲突

代码执行到 i=4 (主串是 ‘A’)，j=4 (模式串是 ‘C’)。

主串：A B A B A B C (当前 i 指向 A)
模式：A B A B C (当前 j 指向 C)
判断：text[i] != pattern[j] (‘A’ != ‘C’)。冲突爆发！

步骤 3：KMP 的魔法（不回退 i，只移动 j）

此时进入 while (j > 0 && text[i] != pattern[j]) 循环。

思考：虽然 ‘C’ 没对上，但 ‘C’ 前面的 A B A B 是对得上的！
查表：查 Next[j-1] 即 Next[3]。
- 我们之前算过，Next[3] = 2。
- 意思是：前 4 个字符里，头部的 2 个 (AB) 和 尾部的 2 个 (AB) 是一样的。
操作：执行 j = next_arr[j-1]，也就是 j = 2。

步骤 4：复活与继续

现在 i=4 (主串 ‘A’)，j=2 (模式串 ‘A’)。

判断：text[i] == pattern[j] (‘A’ == ‘A’)。匹配成功！
操作：j++ (j 变为 3), 循环结束 i++ (i 变为 5)。

接下来继续匹配：

i=5 (主串 ‘B’) vs j=3 (模式串 ‘B’) -> 匹配 -> j 变为 4。
i=6 (主串 ‘C’) vs j=4 (模式串 ‘C’) -> 匹配 -> j 变为 5。

步骤 5：大功告成

代码检测到 j == m (5 == 5)。返回 i - m + 1 = 6 - 5 + 1 = 2。
结果：模式串从主串的索引 2 开始匹配成功

五. 算法流程详解

步骤 1：构建 Next 数组

这是一个“自己匹配自己”的过程。我们需要计算模式串 P 中每个子串 P[0...i] 的 LPS 值。

// ---------------------------------------------------------
// 步骤 1：构建 Next 数组
// 对应 Python: def get_next(pattern)
// ---------------------------------------------------------
vector<int> getNext(const string& pattern) {
    int m = pattern.length();
    
    // 初始化 next_arr，长度为 m，初始值为 0
    // C++ 中使用 vector 替代 Python 的 list
    vector<int> next_arr(m, 0);

    // j 代表前缀的末尾位置，也代表当前 LPS 的长度
    int j = 0;

    // i 代表后缀的末尾位置，从 1 开始遍历
    for (int i = 1; i < m; i++) {
        // 1. 如果不匹配，j 需要回退
        // 这里的回退逻辑和 KMP 匹配主串的逻辑一模一样
        // 注意：j > 0 是防止数组越界
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next_arr[j - 1];
        }

        // 2. 如果匹配，LPS 长度 +1
        if (pattern[i] == pattern[j]) {
            j++;
        }

        // 3. 记录当前位置的 LPS 长度
        next_arr[i] = j;
    }

    return next_arr;
}

步骤 2：主串匹配（KMP Search）

利用构建好的 Next 数组进行搜索。

// ---------------------------------------------------------
// 步骤 2：主串匹配（KMP Search）
// 对应 Python: def kmp_search(text, pattern)
// ---------------------------------------------------------
int kmpSearch(const string& text, const string& pattern) {
    // 边界检查：如果模式串为空，返回 0 (或根据需求返回 -1)
    if (pattern.empty()) return 0;

    // 获取 Next 数组
    vector<int> next_arr = getNext(pattern);
    
    int n = text.length();
    int m = pattern.length();

    // j 代表模式串当前匹配到的位置
    int j = 0;

    // i 扫描主串，永远不回退
    for (int i = 0; i < n; i++) {
        
        // 1. 发生冲突，j 根据 next 数组回退
        // while 循环直到 j回到 0 或者 字符匹配成功
        while (j > 0 && text[i] != pattern[j]) {
            // 回退到上一个已匹配字符对应的 LPS 长度位置
            // 逻辑：pattern[j] 没匹配上，但 pattern[0...j-1] 是匹配的
            j = next_arr[j - 1];
        }

        // 2. 匹配成功，j 前进
        if (text[i] == pattern[j]) {
            j++;
        }

        // 3. 完全匹配成功
        if (j == m) {
            // 返回匹配的起始索引
            // 此时 i 是匹配结束的位置，长度为 m
            return i - m + 1; 
            
            // 如果需要寻找下一个匹配项，可以更新 j：
            // j = next_arr[j - 1];
        }
    }

    // 未找到
    return -1;
}

六. 核心难点：`j = next[j-1]`

很多初学者卡在：为什么失配时，要跳转到 next[j-1]？
假设模式串为 ABABAC，Next 数组为 [0, 0, 1, 2, 3, 0]。

当前 j 指向字符 C (索引 5)。
主串当前字符是 X，C != X，失配。
此时，C 前面的 ABABA (索引 0-4) 是已经完全匹配主串的。
我们要找 ABABA 的最长公共前后缀。查 next[4] (即 j-1)，值为 3。
这表示 ABABA 的头 3 个 (ABA) 和尾 3 个 (ABA) 是一样的。
所以，我们将 j 更新为 3。
这就相当于把模式串向右拉，让模式串索引 3 的字符（即第 4 个字符 B）去和主串的 X 比较。

七. 复杂度分析

时间复杂度：
- 构建 Next 数组需要遍历一次模式串：。
- 匹配过程遍历一次主串：。
- 虽然代码里有 while 循环回退，但 j 最多增加次，也就最多减少次，均摊是线性的。
空间复杂度：
- 需要一个长度为的数组来存储 Next 值。