前缀表#

KMP算法的核心是构建一个前缀表（也称为失配函数），用于在匹配过程中快速跳过已经匹配的部分。前缀表记录了模式串中每个位置之前的最长相等前后缀（正序）的长度。

前缀表的作用#

前缀表的作用是在匹配过程中，当发生不匹配时，能够快速地跳过已经匹配的部分，避免重复比较，从而提高匹配效率。

简单来说，当模式串中的某个位置发生不匹配时，由于在这之前的部分已经匹配成功，如果可以利用已经匹配的部分的信息来跳过一些字符，就可以减少比较的次数。

而前缀表通过记录模式串中每个位置之前的最长相等前后缀的长度，使得在发生不匹配时，可以直接跳过已经匹配的部分，继续进行比较，从而实现线性时间复杂度的字符串匹配。

前缀表的性质#

前缀表具有以下性质：

前缀表的值表示模式串中每个位置之前的最长相等前后缀的长度。
最小循环节的长度可以通过前缀表的最后一个值来计算，公式为：周期长度 = 模式串长度 - 前缀表最后一个值。
前缀表的值可以用来判断模式串是否具有周期性，如果模式串长度是周期长度的整数倍，则说明模式串具有周期性。

NOTE
最小循环节是指一个字符串的最短子串，使得该字符串可以作为这个子串重复若干次构成的字符串的子串。例如，字符串 cabcabca 的最小循环节是 abc，因为 abc 重复三次构成了 abcabcabc，而 cabcabca是其的一个字串。

前缀表的使用#

例如：

模式串：A B A B C 前缀表：0 0 1 2 0

当匹配到 ABAB... 但第五位不是 C 时，已知前四位 ABAB 匹配，查表可知其最长相等前后缀长度为 2（即 AB）。此时不需要从头开始，而是将模式串滑动，让前缀的 AB 对齐到原后缀的 AB 位置，直接从第三位继续比较.

构建前缀表#

如果暴力地构建前缀表，时间复杂度为 $O(n^2)$ ，不过我们可以通过动态规划的思想在 $O(n)$ 的时间内构建前缀表。

对于模式串中的每个位置，我们可以利用前一个位置的前缀表值来快速计算当前的位置的前缀表值。

对于模式串中的每个位置 i 与前缀表 prefix[i]，会出现以下三种情况：

匹配成功：如果第 i 个字符与前一个位置最长相等前后缀的后一个字符相等，则当前最长相等前后缀长度直接加 1，即 prefix[i] = prefix[i - 1] + 1。
失配回退：如果不相等且前一个位置的前缀长度不为 0，说明当前字符虽然没能延长之前的相等前后缀，但可能与之前的更短的相等前后缀组成新的匹配。此时我们需要利用前缀表，将查找范围回退到“前一个相等前后缀”的位置继续尝试。

TIP
相当于将第 i 个字符与前一个位置的最长相等前后缀进行拼接，再求拼接后字符串的最长相等前后缀长度。
完全不匹配：如果回退到开头（前一个位置的前缀长度为 0）依然不匹配，则当前位置的前缀表值为 0。

以下是构建前缀表的步骤：

初始化一个数组prefix，长度与模式串相同，初始值全为0。
使用两个指针i和j，其中i从1开始，j从0开始。
当i小于模式串的长度时：
- 如果模式串的第i个字符与第j个字符相等，则将prefix[i]设置为j + 1，然后将i和j都向右移动一位。
- 如果不相等且j不为0，则将j设置为prefix[j - 1]，继续比较。
- 如果不相等且j为0，则将prefix[i]设置为0，并将i向右移动一位。
最终得到的prefix数组即为前缀表。

KMP算法实现#

以下是KMP算法的实现步骤：

构建模式串的前缀表。
使用两个指针i和j，其中i用于遍历文本串，j用于遍历模式串。
当i小于文本串的长度时：
- 如果文本串的第i个字符与模式串的第j个字符相等，则将i和j都向右移动一位。
- 如果j等于模式串的长度，说明找到了一个匹配，记录匹配的位置，并将j设置为前缀表中j - 1的位置继续匹配。
- 如果不相等且j不为0，则将j设置为前缀表中j - 1的位置，继续比较。
- 如果不相等且j为0，则将i向右移动一位。

代码示例#

以下是KMP算法的C++实现示例：

1
#include <iostream>
2
#include <vector>
3
#include <string>
4

5
// 全局变量：主串（待搜索的字符串）和模式串（要查找的子串）
6
std::string str;      // 主串
7
std::string sub_str;  // 模式串
8

9
// 前缀表 prefix[i] 表示模式串 s[0..i-1] 的最长前缀后缀长度
10
// 这有助于在匹配过程中快速跳过不匹配的部分
11
std::vector<int> initFrefix(const std::string& s, size_t length)
12
{
13
    std::vector<int> prefix(length, 0);  // 初始化前缀表，所有元素为 0
14
    for (int i = 1; i < length; i++)  // 从第二个字符开始遍历模式串
15
    {
16
        int j = prefix[i - 1];  // j 表示当前考虑的前缀长度
17
        // 当字符不匹配时，回退 j，直到找到匹配或 j 为 0
18
        while (j > 0 && s[i] != s[j])
19
            j = prefix[j - 1];
20
        // 如果字符匹配，前缀长度加 1
21
        if (s[i] == s[j])
22
            j++;
23
        prefix[i] = j;  // 设置前缀表的值
24
    }
25
    return prefix;  // 返回计算好的前缀表
26
}
27

28
int main()
29
{
30
    std::cin >> str >> sub_str;
31
    const size_t sub_str_length = sub_str.length(), str_length = str.length();
32

33
    // 计算模式串的前缀表，用于后续匹配
34
    std::vector<int> prefix = initFrefix(sub_str, sub_str_length);
35

36
    // KMP 匹配过程
37
    // i：主串的当前索引
38
    // j：模式串的当前匹配长度
39
    int i = 0, j = 0;
40
    while (i < str_length)  // 遍历主串
41
    {
42
        if (str[i] == sub_str[j])  // 当前字符匹配
43
        {
44
            i++;  // 主串索引前进
45
            j++;  // 匹配长度增加
46
            if (j == sub_str_length)  // 完全匹配模式串
47
            {
48
                // 输出匹配的起始位置（1-based索引）
49
                std::cout << i - j + 1 << std::endl;
50
                // 继续查找下一个匹配，使用前缀表回退 j
51
                j = prefix[j - 1];
52
            }
53
        }
54
        else  // 当前字符不匹配
55
        {
56
            if (j > 0)  // 如果有匹配长度，回退 j
57
                j = prefix[j - 1];
58
            else  // 如果 j 为 0，主串索引前进
59
                i++;
60
        }
61
    }
62
    return 0;
63
}