算法刷题笔记 KMP字符串（C++实现，并给出了求next数组的独家简单理解方式）

题目描述

• 给定一个字符串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
• 模式串P在字符串S中多次作为子串出现。
• 求出模式串P在字符串S中所有出现的位置的起始下标。

输入格式

• 第一行输入整数N，表示字符串P的长度。
• 第二行输入字符串P。
• 第三行输入整数M，表示字符串S的长度。
• 第四行输入字符串S。

输出格式

• 共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ M ≤ 10^6

基本思路

• KMP算法是一个经典的字符串匹配算法。字符串匹配如果使用蛮力算法实现，则最坏情况下的时间复杂度是O(m*n)，其中m和n分别是母串和子串的长度；KMP算法将该时间复杂度优化到了O(m+n)，可以说实现了一个重大的飞跃。
• KMP算法可以分为求next数组和基于next数组的字符串匹配两部分，其中前一部分会更加困难一些。
• 在字符串匹配部分，采用的方法是一种双指针算法，两个指针分别指向母串和子串中的一个待匹配字符。每次都比较两个指针所指向的字符，如果字符相同（发生匹配的情况），则同时将指针移动到下一个位置；如果字符不同（发生失配的情况），则进行分情况讨论：
  • 对于子串的首字符失配，则直接将母串的指针移动到下一个位置；
  • 对于子串的非首字符失配，则根据已经得到的next数组，修改子串指针所指向的位置，避免从头开始匹配带来的冗余消耗。
• next数组的求解是KMP算法最困难的部分，下面进行介绍：
  • next数组中的每一个元素的值，表示从字符串的首个字符开始到当前元素对应的字符结束所构成的子串的最长相同前后缀的长度。注意，这里的最长相同前后缀不包含字符串本身。
  • next数组的首元素需要手动进行初始化，设置其值为0。
  • next数组的构建同样是基于双指针算法完成的。起初，分别设置两个指针指向字符串的第一个字符和第二个字符，之后这两个指针都会向后移动。
    • 当两个指针指向的字符相同时，则当前右指针对应的字符的next数组元素值就是在上一个元素的next数组元素值上自增1；
    • 当两个指针指向的字符不同时，则说明当前的最长相同前后缀分别加上左右指针所指向的字符后，无法继续构成相同的前后缀，因此就需要尝试寻找更短子串构成最长相同前后缀，即代码中的prefix_length = ne[prefix_length - 1]部分。这一部分理解起来比较复杂，因此下面通过一个实例进行介绍。
    • 假设需要构建对应的next数组的字符串是ABACABAB，且当前已经完成匹配的部分是第一个到第三个字符ABA和第五个到第七个字符ABA，第七个字符A对应的next数组值是3。现在左指针指向了第四个字符C，右指针指向了第八个字符B，显然两者不同，因此左右两边的字符串增加了新字符后，ABAC和ABAB显然不是相同的前后缀，因此我们需要使用别的方式计算由这八个字符构成的字符串的最长相同前后缀。
    • 直观上我们发现，如果需要构建最长相同前后缀，那么就需要两个条件：加入的新字符完全相同、加入新字符前的前缀和后缀完全相同。这样，就可以产生一个巧妙的构思：既然当前字符串的最长相同前后缀分别增加一个新字符后无法继续构成最长相同前后缀，那么我们能不能退而求其次，不是使用当前的最长相同前后缀，而是第二长相同前后缀，来构建下一个最长相同前后缀呢？这是因为，第二长相同的前后缀也满足加入新字符前的前缀和后缀完全相同，并且修改了前缀和后缀后，前缀的下一个字符也会随着前缀更改一次，说不定就可以和右指针新插入的字符相同了。
    • 例如，对于ABACABA，最长的相同前后缀是ABA（前三个字符和后三个字符），但是最长的相同前后缀再增加第八个字符B后，构成的前后缀分别是ABAC和ABAB，显然不相同。但是，如果使用第二长前后缀A（即第一个字符和第七个字符），增加一个字符B后，仍然可以构成相同前后缀AB。因此，在字符串当前的最长相同前后缀无法继续构成下一步的最长相同前后缀时，我们可以使用第二长的相同前后缀继续进行尝试，如果还不行则使用第三长的相同前后缀…直到找到可以继续构成相同前后缀的相同前后缀或确定不存在可以构成相同前后缀的相同前后缀（因为一个字符串的相同前后缀的个数是有限的）。现在的问题就是如何找出一个字符串的第二长相同前后缀。
    • 对于字符串ABABABA，其最长相同前后缀是ABA，包含三个字符，那么第二长的相同前后缀如果存在，则一定只包含两个字符或者一个字符，所以我们需要比较该字符串的前两个字符和后两个字符，以及第一个字符和最后一个字符。由于我们已经知道了ABA是最长相同前后缀，所以后两个字符实际上就是第二个和第三个字符，最后一个字符实际上就是第三个字符，因此问题就转换为了比较该字符串的前两个字符和第二个第三个字符，以及字符串的第一个字符和第三个字符是否相同的问题，其实也就是前三个字符构成的字符串ABA的最长相同前后缀问题！
    • 由于我们求解next数组的过程是顺序进行的，因此我们已经计算出了前三个字符ABA对应的next数组元素分别为001，因此我们可以得出对于ABA，其最长相同前后缀的长度为1，因此对于字符串ABABABA，其第二长相同前后缀的长度也是1。因此，在最长相同前后缀ABA无法继续构成最长相同前后缀时，我们使用第二长的相同前后缀尝试继续构建最长相同前后缀，构建出了AB，成功！

实现代码

#include <iostream>
using namespace std;

// 创建一个静态数组ne作为next数组
const int n = 1e5 + 10;
int ne[n];

// 获取next数组的函数
// 传入的参数分别是字符串的长度N和字符串P
// 函数根据传入的参数计算next数组
void get_next(int N, const string& P)
{
    // 首先将第一个元素对应的next值设置为0
    ne[0] = 0;
    // 定义并初始化两个指针
    int prefix_length = 0, j = 1;
    // 通过循环的方式求解next数组，直到完成对字符串的遍历
    while(j < N)
    {
        // 情况1：两个指针所指向的字符相同，则说明最长相同前后缀可以同时自增，并记录结果
        if(P[prefix_length] == P[j])
        {
            ++ prefix_length;
            ne[j] = prefix_length;
            ++ j;
        }
        else
        {
            // 情况2：两个指针所指向的字符不同且第一个指针并不是指向字符串首字符，则根据next数组找出次最长相同前后缀
            if(prefix_length != 0) prefix_length = ne[prefix_length - 1];
            // 情况3：两个指针所指向的字符不同，且第一个指针指向字符串首元素，则直接将此处记录为0即可
            else
            {
                ne[j] = 0; 
                ++ j;
            }
        }
    }
}

// 进行KMP字符串匹配的函数
// 传入的参数分别是子串的长度N、子串P、母串的长度M、母串S
// 函数会在控制台输出子串P在母串S中所有出现位置的首字符下标
void KMP_search(int N, const string& P, int M, const string& S)
{
    // 首先根据子串P获取其对应的next数组
    get_next(N, P);
    // 定义并初始化母串和子串的指针
    int pp = 0, sp = 0;
    // 通过循环进行字符串匹配，当超出母串长度时停止循环
    while(sp < M)
    {
        // 情况1：当前母串和子串的对应字符相同，则指针同时自增比较下一个元素
        if(P[pp] == S[sp]) 
        {
            ++ pp; 
            ++ sp;
        }
        else
        {
            // 情况2：当前母串和子串的对应字符不同，且不是发生在子串第一个元素，则基于next数组修改子串指针
            if(pp != 0) pp = ne[pp - 1];
            // 情况3：当前母串和子串的对应字符不同，且发生在子串的第一个元素，则直接将母串指针自增
            else ++ sp;
        }
        
        // 每一次当子串遍历完成一次，则输出一次出现下标，并基于next数组修改子串指针
        if(pp == N)
        {
            cout << sp - pp << " ";
            pp = ne[pp - 1];
        }
    }
}

int main(void)
{
    int N, M;
    string P, S;
    cin >> N >> P >> M >> S;
    KMP_search(N, P, M, S);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83