理解KMP算法的实现过程。

【2023年02月02日第1.0版本。】

一、关于KMP算法。

KMP算法是一个字符串匹配算法，用于在一串较长的字符串中快速地查找到一串给定的已知的字符串出现的起始位置。其效率要优于朴素的算法（普通的、直接的、工作量大的）。朴素的字符串匹配算法的时间复杂度为O(n*m)，KMP算法的时间复杂度为O(n + m)。这个优化效果着实很哇塞了，那么KMP算法是如何实现的呢？和我一起来（试图）理解一下KMP算法的实现过程吧~

二、关于朴素的字符串匹配算法。

等等！先别急着试图理解KMP算法，如果你还不知道如何使用朴素的字符串匹配算法，请停下来，让我写给你听，否则你不能体会到KMP算法的重要意义，甚至你无法理解KMP算法中的基础概念。若你不想看这个无聊的内容，可以跳过，但是KMP算法的讲解也会在下面这个例题的基础之上，请注意查看例题内容。

【例题】

给定一个字符串s，以及一个字符串 p ，称前者为文本串，是 p 串可能存在的最大字符区间，称后者为模式串，是需要查找的串。所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 p 在字符串 s 中作为子串出现且最多出现一次。

求出模式串 p 在字符串 s 中出现的位置的起始下标，如果字符串 s 中未出现模式串 p，则输出”Not Find!”。

给定文本串 s 的长度为 m = 15，内容为 ababaababababba

给定模式串 p 的长度为 n = 7，内容为 abababb

现在，我们开始使用朴素算法做匹配工作。

1.首先，我们需要把两个字符串存储到字符串数组中。在我这里，我规定两个字符串一定要从数组的下标1开始存储，这也使得后面的KMP算法更易于理解。我们得到文本串 s[m] 和模式串 p[n]，同时初始化指针 i 指向 s[m] 的首个元素 s[1] ，即 i = 1；初始化指针 j 指向 p[n] 的首个元素 p[1] ，即 j = 1。

const int N = 1e6 + 10;         // 字符串的最大长度。
char s[N];                      // 定义文本串。
char p[N];                      // 定义模式串。
scanf("%s%s", s + 1, p + 1);    // 读入两个字符串，从下标1开始存储。

2.然后，我们可以即刻开始朴素的逐个匹配过程了。

从 s 串的首个元素开始逐个往后匹配，如果发现 p 中的某个元素与 s 对应的元素不匹配，移动到 s 串的第二个元素开始再次从 p 串的收割元素逐个往后匹配，知道某次 p 串中的所有元素全部匹配成功，说明查找到了 p 串；或者在遍历整个 s 串后也没有完全匹配，说明 s 串中没有出现子串 p 。

int idx = -1;                       // 记录s串中p串出现的位置下标。
for (int i = 1; i <= m; i++)
{
    bool flag = true;               // 设置查找成功的标志。
    for (int j = i; j <= n; j++)
    {
        if (s[i + j - 1] != p[j])   // 逐个往后匹配，发现不匹配的元素
        {
            flag = false;           // 标志匹配失败
            break;                  // 结束本次匹配
        }
    }
    if (flag == true)// 若某次匹配结束后，标志仍然匹配成功，表明查找到 p 串，记录所需的信息，结束所有匹配工作。
    {
        idx = i;                // 记录s串中p串出现的位置下标。
        break;
    }
}

朴素算法过程结束。

三、KMP算法的原理。

像上面这样需要逐个检查数组中每个元素的方法，一般称为朴素的或者暴力的方法，其缺点是对每一个元素都执行了工作，在这个过程中，会执行大量的无效的工作，这些工作对获取答案的贡献值为0，因此我们希望跳过这些完全不可能有用的或者重复的工作部分，KMP算法就能帮助我们做到这一点，从而提高了效率。

以前面的例题为例讲解KMP算法的原理。

1.哪些部分是需要跳过的？我们需要来走一遍朴素算法的过程，去发现捷径。

开始，i = 1; j = 1; s[i] = ‘a’; p[j] = ‘a’;

发现 s[1] 与p[1] 匹配（相等），那么 j 要指向 p 的下一个元素，与 s 的第 i + j - 1 个元素匹配，即 s[i + j - 1] 。

此时 s[2] 与 p[2] 匹配成功，j 指针往后移动，逐个判断。

经过逐个判断，发现 s[1] ~ s[5] 与 p[1] ~ p[5] 的5个元素都匹配成功。但是 s[6] 与 p[5] 匹配失败。

按照朴素的算法，此时应该立即结束本次匹配，将 i指针移动到下一位，j 指针指向 p 的第一个元素，再次从 p 的头部开始匹配。如下：

【i = 2开始匹配】：

图中紫色框框的区间是上一次匹配过程中确定的 s 串与 p 串的前端一部分相匹配的区间串。

好的，我们继续走朴素算法的过程：

上图中，发现 s[2] 与 p[1] 不匹配，结束本次匹配，i 指向 s 的下一个元素，j 指向 p 的首个元素。

【i = 3 开始匹配】：

经过逐个匹配，发现 s[3] ~ s[5] 的元素与 p[1] ~ p[3] 的元素都匹配成功，但 s[6] 与 p[4] 匹配失败。结束本次匹配，i指向下一个元素，j 指向p的首部。

【i = 4 开始匹配】：

s[4] 与 p[1] 匹配失败，结束本次匹配，i 指向 s 的下一个元素，j 指向 p 的首个元素。

【i = 5开始匹配】：

经过逐个匹配，发现 s[5] 与p[1] 匹配成功，但 s[6] 与 p[2] 匹配失败，结束本次匹配，i 指向 s 的下一个元素，j 指向 p 的首个元素。

【i = 6 开始匹配】：

至此我们走出了那个紫色框框，开始从 s[6] 往后匹配，在得到紫色框框的区间后，我们一直是在为了让 s[6] 匹配成功，s[6] 是延伸匹配的下一个元素，如果 s[6] 与对应的 p[j] 匹配失败，成功匹配的字符串就不能延伸，即可结束匹配。

2.如何跳过无效工作？

在前面过程的【i=3开始匹配】、【i=5开始匹配】和【i=6开始匹配】的匹配过程中，都对 s[6] 进行了匹配，其他匹配过程，都是不可能匹配成功的过程。

【i=3开始匹配】和【i=5开始匹配】都在紫色区间内得到了部分成功匹配，这意味着如果 s[6] 匹配成功，成功匹配区间就可以延伸一位，这是我们并不知道 s[6] 能否匹配成功，我们可以跳过不可能匹配成功的部分，但对于可能成功的部分，我们必须要去尝试，如果整串匹配成功了呢？跳过岂不是亏大了？

所以，如果在得到那个紫色区间后，有人告诉我下一个成功匹配的绿色部分的长度的话，就可以直接将 s[6] 与 p 上的这个长度的下一位做匹配，这同时跳过了那些完全不可能成功的和该长度内的元素的匹配过程。

那么，哪个小可爱会过来告诉我这个重要的信息呢？它能预知未来么？

四.【插播】：关于字符串的前缀和后缀

字符串的前缀：以原字符串的首位元素为本字符串的首位元素的小于整个字符串长度的任意子串。

字符串的后缀：以原字符串的末位元素为本字符串的末位元素的小于整个字符串长度的任意子串。

规定：长度为1的字符串没有前缀和后缀。

例如：本题中的模式串 abababb ，其前缀包括：{a},{ab},{aba},{abab}, {ababa}, {ababab}；其后缀包括：{b},{bb},{abb},{babb},{ababb},{bababb}。

五.召唤 Next 数组

KMP算法中就有这么一个小可爱，在我们开始执行匹配工作之前就知道了我们每一轮匹配失败后，下一步该走到哪里去，它的名字叫Next数组，正如它的名字那样，也正是我们需要的，在我们失败时，它将告诉我下一步最好该走向何方。

1.Next数组的作用。

我们前面提到，当 s[6] 匹配失败并且得到一个匹配成功的区间（那个紫色区间），这个区间一定是 p 的一个前缀，我们需要知道下一个可能使得 s[6] 匹配成功的 p 的前缀的长度，这个前缀一定是当前匹配成功区间（紫色区域）的后缀，又因为当前匹配成功区间与对应 p 上的区间相同，所以这个前缀就是当前匹配成功区间的前缀，那么我们所需要的就是：当前得到的匹配成功区间的一个相等前后缀的长度，而为了不错过任何一个可能性，我们需要这个长度达到最大。

Next数组中存储的就是每次得到的那个匹配成功的区间的最大相等前后缀的长度。

得到了这个长度，那么最大相等前后缀内的元素是匹配成功的，就不需要再做匹配了，直接从这个前后缀的下一个元素开始与 s[i] 进行匹配即可。

如上图，{aba} 就是 紫色区间的最大相等前后缀，长度为3，这时直接将 s[6] 与 p[3 + 1] 进行匹配，紫色区间内的元素没有再进行匹配的过程。

现在我们已经有了这样一个贴心的小可爱，快让小可爱带着我们体验一遍KMP的匹配过程吧~

上面的图中已经第一次使用了Next数组，然我们接着：

上图中，Next数组告诉我们 {ababa} 的最大相等前后缀长度是3，于是我们直接跳过这个区间，将 j 指向 p 上第3个元素的下一位，将 p[4] 与 s[6] 进行匹配，发现匹配失败， 结束本轮匹配。这时我们知道 s[3] ~ s[5] 是本轮匹配成功的部分，我们可以让 Next 数组告诉我们这个区间的最大相等前后缀长度，继续跳过无效的匹配过程，Next数组告诉我们{aba}的最大相等前后缀长度是1，那么将 j 指向 p 上第1个元素的下一位，将 p[2] 与 s[6] 进行匹配：

上图中紫色区间仍是上一轮中匹配成功的区间。发现 s[6] 与 p[2] 匹配失败，结束本轮匹配。这时 Next 数组又来告诉我们，本轮匹配成功区间 {a} 的最大相等前后缀长度为0，将 j 指向 p 上第0个元素的下一位，将 p[1] 与 s[6] 进行匹配：

每轮匹配都是从 s[6] 开始的，如果 s[6] 匹配失败，就将 j 跳到 p 上下一个可能使得 s[6] 匹配成功的位置，然后本轮匹配结束，如果本轮中 s[6] 匹配成功，那么延伸本轮成功匹配的区间，继续往后逐个匹配。

本轮中 s[6] 与 p[1] 匹配成功，延伸本轮成功匹配的区间，继续往后逐个匹配：

过程中发现 s[12] 与 p[7] 匹配失败，贴心的 Next 数组告诉我们，本轮中成功匹配区间的最大相等前后缀长度为4，那么 j 指向 p 上第4个元素的下一个元素，结束本轮匹配。

发现 s[12] 与 p[4 + 1] 匹配成功，那么本轮的成功匹配区间延伸，继续往后匹配。

经过逐个匹配，发现 p 串的所有元素全部匹配成功，结束所有匹配过程。模式串 p 在文本串 s 中出现的位置的起始下标为 14 - 7 + 1 = 8。

在KMP算法的匹配过程中，可以发现，s 上的指针 i 一直在跟着 p 上的指针 j 往后移动，但当匹配失败， j 减小为最大相等前后缀的长度时，i 并没有跟着 j 变小；而在朴素算法的匹配过程中，当匹配失败时，i 放弃了那段已经匹配成功的区间，从这次开始匹配的位置的下一个位置再次匹配，这个过程执行了许多无效的且重复的工作。

如果已经获取了Next数组，KMP算法的代码如下：

// 已经获取了 Next[] 数组
int idx = 0;
for (int i = 1, j = 0; i <= m; i++)
{
    // 遇到 s[i] 与 p[j + 1] 匹配失败，将j指向当前已经成功匹配区间的最大相等前后缀的最后一个元素，直到 p[i] 匹配成功或者 j 退回到0。
    while (j != 0 && s[i] != p[j + 1])
        j = Next[j];

    // 如果 s[i] 与 p[j + 1] 匹配成功，延长成功匹配的区间。
    if (s[i] == p[j + 1])
        j++;

    // 如果 p 串的所有元素全匹配成功，记录 p 串在 s 串中出现的位置的起始下标；结束所有匹配工作。
    if (j == n)
    {
        idx = i - j + 1;
        break;
    }
}

六、获取 Next 数组

如此贴心的小可爱，我们怎样才能得到它？

它就来自于你要找的那个她的身上。

没错，是她，在指引着我，让我不在一个地方留恋，让我不去回头，让我看清前方。

在KMP算法的匹配过程中，每当匹配失败，我们就需要得到本轮成功匹配区间的最大相等前后缀长度；而本轮成功匹配的区间也是 p 串的一个前缀，它的长度就是指针 j -1 的值，因为 j 指向的是当前正在匹配的元素，成功匹配的区间是 p[1]~p[j - 1]；所以，我们需要提前获取 p 串的所有前缀的最大相等前后缀的长度，并存储到 Next 数组中，就得到了我们需要的 Next 数组小可爱。

那么，对于 p ：{abababb}

长度为1的前缀为{a}，最大相等前后缀长度为0，把此值存储到 Next[1] 中；

长度为2的前缀为{ab}，最大相等前后缀长度为0，把此值存储到 Next[2] 中；

长度为3的前缀为{aba}，最大相等前后缀为{a}，长度为1，把此值存储到 Next[3] 中；

长度为4的前缀为{abab}，最大相等前后缀为{ab}，长度为2，把此值存储到 Next[4] 中；

长度为5的前缀为{ababa}，最大相等前后缀为{aba}，长度为3，把此值存储到 Next[5] 中；

长度为6的前缀为{ababab}，最大相等前后缀为{abab}，长度为4，把此值存储到 Next[6] 中；

可以顺便求出整个 p 串的最大相等前后缀长度，为0，把此值存储到 Next[7] 中，可能会有用哦。

我们已经知道，长度为1的字符串没有前缀和后缀，即最大相等前后缀的长度为0，Next[1] = 0；

然后要获取p上长度为2的前缀的最大相等前后缀 Next[2]，由于{ab}的只有前缀为{a}，后缀为{b}，所以直接把{ab}，的前缀和后缀匹配即可：

图中 i 指向 p 上当前长度区间的最后一个元素，j 指向上一个前缀的最大相等前后缀的最后一个元素。

p[2] 与 p[1] 匹配失败，本次匹配结束，{ab} 的最大相等前后缀的长度就是 j 的值，Next[2] = 0。接下来要获取p上长度为3的前缀的最大相等前后缀Next[3]，i 指向下一个元素增加长度。上一个区间的最大相等前后缀长度为0，j 保持指向0。

p[3] 与 p[1] 匹配成功，可以看到图中橙色框框中，上面一行是{aba}的前缀，下面一行是{aba}的后缀。p 上长度为3的前缀的最大相等前后缀长度就是 j+1 的值，Next[3] = 1;

接下来获取 p 上长度为4的前缀的最大相等前后缀长度，i 指向下标4，j 指向下标1，由于上一次匹配中，已知了一部分成功匹配的最大相等前后缀区间，所以不需要再对该区间的元素执行匹配。s[4] 与 s[2] 匹配成功，那么最大相等前后缀延长，Next[4] = 2。

接下来获取 p 上长度为5的前缀的最大相等前后缀长度，p[5] 与 p[3] 匹配成功，最大相等前后缀延长，Next[5] = 3。

获取p上长度为6的前缀的最大相等前后缀长度，p[6] 与 p[3] 匹配成功，最大相等前后缀延长，Next[6] = 4。

最后获取整个 p 串的最大相等前后缀长度，p[7] 与 p[5] 匹配失败。

此时已知了 Next[1] = 0, Next[2] = 0, Next[3] = 1, Next[4] = 2, Next[5] = 3；

此时成功匹配的最大相等前后缀不能延长，为了使 p[7] 匹配成功，我们需要将已经成功匹配的前缀缩短一点来比较，缩短到什么位置呢？不需要逐个比对，由于已经匹配成功的前缀的长度一定比当前的长度7要小，所以这个区间的最大相等前后缀在此之前已经被记录在Next 数组中，我们直接使用它，把 p[7] 与 p[Next[4] + 1] 进行匹配。

图中紫色框框是上一轮匹配中成功匹配的区间，绿色框框内是紫色框框区间的最大相等前后缀。

没错，那个紫色框框又出现了。

此时 p[7] 与 p[3] 匹配失败，我们需要把 j 跳到本轮匹配成功的区间的最大相等前后缀长度的位置，将 p[6] 与 p[Next[2] + 1] 进行匹配。

此时 p[7] 与 p[1] 匹配失败，最大相等前后缀就是 j 的值，Next[7] = 0。

获取 Next 数组完成。

在获取Next数组的过程中，我们可以看到KMP算法匹配字符串的影子，i 指针没有回退，当遇到不匹配的元素时，Next 数组需要自己给自己提供信息，KMP匹配需要 Next 提供信息。

获取Next[]数组的代码如下：

// 获取 Next[] 数组。
// Next[1] = 0是已知的，所以i从下标2开始，在 p 串上操作，i小于等于p的长度n
for (int i = 2, j = 0; i <= n; i++)
{
    // 遇到 p[i] 与 p[j + 1] 匹配失败，将 j 指向已经成功匹配区间的最大相等前后缀的最后一个元素，直到 p[i] 匹配成功或者 j 退回到0。
    while (j != 0 && p[i] != p[j + 1])
        j = Next[j];

    // 如果 p[i] 与 p[j + 1] 匹配成功，最大相等前后缀延长。
    if (p[i] == p[j + 1])
        j++;

    // 没记新增一个元素，要记录新增这个元素后的长度的最大相等前后缀的长度。
    Next[i] = j;
}

七、用KMP算法完成例题的完整代码示范

【例题】：

给定一个字符串s，以及一个字符串 p ，称前者为文本串，是 p 串可能存在的最大字符区间，称后者为模式串，是需要查找的串。所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 p 在字符串 s 中作为子串出现且最多出现一次。

求出模式串 p 在字符串 s 中出现的位置的起始下标，如果字符串 s 中未出现模式串 p，则输出”Not Find!”。

【输入格式】：

第一行输入整数 m，表示字符串 s 的长度。

第二行输入字符串 s。

第三行输入整数 n，表示字符串 p 的长度。

第四行输入字符串 p。

【输出格式】：

共一行，输出出现位置的起始下标（下标从 1 开始计数）。

【数据范围】：

1 <= n <=m <= 1000000

【输入样例】：

15
ababaababababba
7
abababb

【输出样例】：

8

【代码示范】：

// KMP算法的基本使用。（c++版本）
// 作者：TimTiming（ACwing网站ID）
// 日期：2023年2月2日
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
char s[N], p[N];
int Next[N];

int main()
{
    int m, n, idx = -1;
    scanf("%d%s", &m, s + 1);
    scanf("%d%s", &n, p + 1);

    // 获取Next[]数组。
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j != 0 && p[i] != p[j + 1])
            j = Next[j];
        if (p[i] == p[j + 1])
            j++;
        Next[i] = j;
    }

    // 执行KMP算法匹配。
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j != 0 && s[i] != p[j + 1])
            j = Next[j];
        if (s[i] == p[j + 1])
            j++;
        if (j == n)
        {
            idx = i - j + 1;
            break;
        }
    }
    if (idx == -1)
        printf("Not Find!\n");
    else
        printf("%d\n", idx);
    return 0;
}

【你能多久找到她，不在于你经历了多少次失败，而取决于当你发现这个人很像她，但又不是她的时候，你多久才能彻底放下，去尝试下一个可能。】------KMP