KMP算法详解

文章目录

• 一、引言
• 二、暴力匹配算法（Brute Force）
• 三、好像可以优化一下？
• 四、`next`数组
• 五、进行匹配
• 六、举例说明
• 七、对简洁板子代码的解读
• 八、获取模式串所有出现的位置
• 九、最终BOSS：时间复杂度的证明
• 答疑
• 例题解析
• 参考文献

一、引言

KMP算法（The Knuth-Morris-Pratt Algorithm）绝对是我到目前为止学过的最毒瘤的算法之一。

我看KMP的代码就跟看天书一样，云山雾罩的。

这个KMP算法非常的玄妙，理解起来颇为费劲。

本篇文章我会尽力讲的通俗易懂，用启发式的方法阐述Knuth、Morris和Pratt三位大神的思想。

（Knuth爷爷敲腻害的，Latex的发明人就是他~）

一些约定：
匹配串 – text/long string，长的，也叫文本、主串（以下就以“长串”称呼），长度为 n n n，数组记作l[0...n-1](l=long)
模式串 – pattern，短的，长度为 m m m，数组记作p[0...m-1](p=pattern)
我们要在匹配串（长的）里面找模式串（短的）第一次出现的位置。

二、暴力匹配算法（Brute Force）

要提字符串匹配，肯定绕不开暴力匹配算法。

优化算法就是建立在暴力的基础之上的。

暴力算法很直观，就是枚举长串中的每个子串，判断这个子串是否与模式串相等。

下面这张图展示了长串= ababcd \text{ababcd} ababcd，模式串= abc \text{abc} abc的情况。

我们可以把算法流程形象地理解为：模式串从第 0 0 0位开始，每次向后移一位，然后比较上下两个字符串的对齐部分是否相等。

如果相等，返回此时模式串的位置；如果都不想等，返回 − 1 -1 −1。

我们可以很轻松愉悦地写出这部分的代码：

int find(const char* l/*长的*/, const char* p/*短的*/)
{
	int n = strlen(l), m = strlen(p);
	// 分别为长串和模式串的长度 
	for(int i = 0; i <= n - m; ++i)
	// 枚举模式串在长串中出现的位置（相当于一直让模式串往后移）
	{
		bool flag = true; // 是否匹配
		for(int j = i; j < i + m; ++j)
		// 考察每个字符
		{
			if(l[j] != p[j - i]) // 如果对应字符不匹配
			{
				flag = false;
				break; // 失败，退出 
			} 
		}
		if(flag) // 若匹配成功
		{
			return i; // 返回匹配到的位置 
		} 
	}
	return -1; // 没有匹配的位置，返回-1
	// 如果有的话在前面就返回了，执行不到这里
}

因为思路很简单，这里就不过多赘述了。

暴力匹配算法的时间复杂度为 O ( m ( n − m + 1 ) ) = O ( n m ) O(m(n-m+1))=O(nm) O(m(n−m+1))=O(nm)。

顺便说一下：STL中的string::find和中的函数strstr都采用的是暴力匹配算法。

三、好像可以优化一下？

当然，暴力算法在我们眼中看起来很蠢。

有的时候明明很显然不可能匹配上的位置，暴力算法还要考察一下。

有没有更聪明的办法呢？

下面为了更加直观，我们用色块表示字符串。

相同颜色的色块表示相同的字符串。

我们考虑一种非常特殊的情况。

假如长串和模式串的情况是这样的：

其中浅蓝色的部分是相同的字符串，两串中的“蓝绿蓝”部分是匹配的，且淡绿色的部分不包含浅蓝色的部分。

而后面的红色和黄色部分是不能匹配的。

那我们下来怎么办呢？还傻乎乎地把模式串往后仅仅移一位吗？

显然，因为淡绿色部分不包含浅蓝色部分，仅仅往后移一位仍然是不可能匹配的。

事实上，我们可以看出，下一个可能匹配的位置是这里：

只有让模式串跳到这个位置才可能进行下一个匹配，在此之前都是不可能匹配的。

采用这种策略，我们可以直接跳很远，大幅度减少计算的次数。

四、next数组

好了，推广到更一般的情况，现在我们发现长串和模式串的一部分是匹配的，且这部分是模式串的一个前缀。

那么，我们怎么知道绿色部分是否有前缀和后缀是相等的呢？

要解决这个问题，就需要知道模式串的每个从头开始的子串的最长的相等前缀和后缀。

几点解释：
(1) 从头开始的子串就是模式串的前缀，后面所谓的前缀可以理解为模式串的“前缀的前缀”。

(2) 为什么要考虑每个从头开始的子串？因为你不知道长串和模式串有多少是匹配的，所以得应对匹配部分长度等于任何值的情况。

(3) 为什么是最长的相等前缀和后缀？因为要保证淡绿色的部分不可能包含浅蓝色的部分，这样我们才不会漏掉可能匹配的位置。

举个例子，已经匹配的字符串是

它的最长的相等前缀和后缀是 aba \text{\color{#b4c6e7}aba} aba。

那如果我们仅将 a \text{\color{brown}a} a作为浅蓝色部分的话，就必须这样跳：

但是，这忽略了一个很显然的情况：

在这个位置也是可能匹配的。

所以，为了避免“跳过了”，必须让前缀和后缀的长度尽可能大。

那么，现在我们的任务就是求出每一个位置相等的前缀和后缀的长度。

我们定义next数组，next[j]表示p[0...j-1]的不等于自身的相等前缀和后缀的长度（p为模式串）。

（一定注意：是0~j-1，不包含第j个字符。

这样定义可以简化代码。

）即：令k = next[j]，则p[0...k-1] = p[j-k+1...j]。

若p[0...j-1]没有相等的前缀和后缀，记next[j] = 0。

特别地，令next[0] = -1（后面讲为什么）。

举个栗子：

在字符串 abacaba \text{abacaba} abacaba中，next[6] = 2，因为p[0...5] = abacab，其最长相等前缀和后缀是 ab \text{ab} ab，长度为 2 2 2。

小练习：求这个字符串的next数组： ijkjioijkji \text{ijkjioijkji} ijkjioijkji
答案： − 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 2 , 3 , 4 -1,0,0,0,0,1,0,1,2,3,4 −1,0,0,0,0,1,0,1,2,3,4

现在考虑怎么求next数组。

如果用暴力的话，时间复杂度高达 O ( m 3 ) O(m^3) O(m3)。

然而，我们其实有 O ( m ) O(m) O(m)的算法。

递推是降低复杂度的一个有效方法。

考虑已经知道了next[0...j]，如何求出next[j+1]。

回顾一下next的性质：设k = next[j]，则p[0...k-1] = p[j-k...j-1]。

现在对于next[j+1]，如果说p[k] == p[j]，那我们只需要把最长相等前缀和后缀延长一格就好了，next[j+1] = next[j] + 1。

如下图所示。

但如果p[k] != p[j]，这就麻烦了。

我们不能仅仅延长上一个位置的前缀和后缀。

怎么办呢？
假设最终我们求得的next[j+1] = t+1（加的 1 1 1是新增的相等的字符p[t] == p[j]），则p[0...t-1] = p[j-t...j-1]，且t < k。

而我们又有p[0...k-1] = p[j-k...j-1]，那么把右边的p[j-k...j-1]映射到左边的p[0...k-1]，就会得到p[k-t...k-1] = p[j-k...j-1]。

结合p[0...t-1] = p[j-t...j-1]，就有p[0...t-1] = p[k-t...k-1]。

如下图所示：

这说明了什么？这说明了p[0...k-1]本身也有前缀和后缀是相等的。

因为next[j+1] = t+1，t+1是p[0...j]的最长相等前缀和后缀的长度，那么t就是p[0...j-1]的最长相等前缀和后缀的长度。

这里的最长保证了t同样也是p[0...k-1]的最长相等前缀和后缀的长度。

因此：t = next[k]。

这给我们一个思路：求next[j+1]的时候，令k = next[j]，如果出现p[k] != p[j]的情况，就令k = next[k]（此时k的值就是t），看看现在满不满足p[k] == p[j]，如果满足，就令next[j+1] = k+1，否则就不断套娃，一直套到p[k] == p[j]为止。

这样，让k从大往小依次尝试，只要尝试成功就给next[j+1]赋值并退出迭代，从而保证了k一定是尽可能大的。

如果一直不满足怎么办？在这种情况下必然会导致最终k == 0，如果此时仍有p[k] != p[j]，再令k = next[k]，就有k = -1。

此时我们加个特判，如果k == -1，说明没有相等的前缀和后缀，令next[j+1] = 0即可。

温馨提示：next是头文件中的一个函数名。

如果你引用了该头文件，请避免使用next作为数组名。

这部分的代码实现：

void GetNext(const char* p/*模式串*/, int* next/*模式串的next数组*/)
{
    int m = strlen(p); // m是模式串p的长度
    next[0] = -1; // 递推的初始条件，不要忘记
    for(int j = 0; j < m - 1; ++j) // 循环j从0到m-2
    {
        // 求next[j + 1]
        int k = next[j];
        while(k != -1)
        // 当k != -1时，一直套娃
        {
            if(p[k] == p[j])
            // 匹配成功，延长前缀和后缀
            {
                next[j + 1] = k + 1;
                break;
            }
            else k = next[k];
            // 否则继续套娃，寻找更短的相等前缀和后缀
        }
        if(k == -1) next[j + 1] = 0;
        // 匹配不成功，next[j + 1] = 0
    }
}

这份代码虽然没有板子代码简洁，但更容易理解。

后面我们会讲解简洁的板子代码到底是如何运作的。

五、进行匹配

我们终于花了很大力气求出了next数组，现在就要派上用场了。

匹配的部分比较简单，只要一直跳跳跳就行了。

回顾我们第三部分讲述的内容。

当出现下面这种情况时：

就要让模式串跳到这里：

此时如果匹配，就万事大吉了；如果不匹配怎么办呢？
在这种情况下，我们看到，长串和模式串仍然有浅蓝色部分是匹配的。

其实我们可以继续套用刚才的过程。

在浅蓝色的部分继续寻找有没有相等的前缀和后缀，如果有的话，那就可以继续跳：

其中黑框标出来的部分就是浅蓝色的部分的相等的前缀和后缀。

如果还是不匹配，就对黑框中的部分继续套娃，一直套到匹配或者没有相等的前缀和后缀为止。

我们令一开始匹配的长度为j，浅蓝色的部分长度为k = next[j]，模式串的第j位与长串的第i位失配。

跳一次（模式串往右移j - k = j - next[j]格）：

此时我们要判断l[i] == p[j']是否成立，其中j' = k = next[j]。

所以我们可以直接把这个过程写成j = next[j]。

这又成了类似于计算next数组一样的套娃过程。

当一直套到next[j] == 0即长串和模式串的匹配部分没有相等的前缀和后缀，且l[i] != p[j]（j = 0）时，再令j = next[j]，就有j = -1，此时我们加一个特判：当j == -1时，就直接像暴力算法那样++i，j = 0。

注意：这里的i与暴力算法中的i含义不同。

暴力算法中的i指的是l[i]与p[0]对齐，而这里的i是l[i]与p[j]对齐，与p[0]对齐的是l[i-j]。

那么j = 0意味着l[i]与p[0]对齐，就与暴力算法一样了。

这部分的代码实现：

int KMPSearch(const char* l/*长串*/, const char* p/*模式串*/)
{
    int n = strlen(l), m = strlen(p); // n和m分别是长串l和模式串p的长度
    int* next = new int[m]; // 开辟next数组的空间
    GetNext(p, next); // 调用GetNext函数获取模式串p的next数组
    int i = 0, j = 0; // l[i]与p[j]匹配
    while(i < n && j < m)
    {
        if(j == -1) // j == -1说明没有相等的前缀和后缀
        {
            ++i; // 匹配失败，i加一
            j = 0; // l[i]与p[0]对齐
        }
        if(l[i] == p[j]) // l[i]与p[j]匹配成功，继续往下
        {
            ++i;
            ++j;
        }
        else j = next[j];
        // 否则p往后跳，进行套娃
    }
    delete []next; // 释放next数组的空间
    if(j == m) return i - j; // 匹配成功，返回匹配的位置i-j
    else return -1; // 匹配失败，返回-1
}

六、举例说明

接下来我们举一个例子来理解（请配合代码食用）。

长串l： abacabacabadabacabae \text{abacabacabadabacabae} abacabacabadabacabae
模式串p： abacabae \text{abacabae} abacabae

🍒​求next数组

m = strlen(p) = 8
next[0] = -1
然后j从0循环到m-2

• j=0：k = next[j] = -1，匹配直接失败，next[j+1] = next[1] = 0
• j=1：k = next[j] = 0，p[k] != p[j]（'a' != 'b'），故令k = next[k]，k = -1，匹配失败，next[j+1] = next[2] = 0
• j=2：k = next[j] = 0，p[k] == p[j] == 'a'，匹配成功，next[j+1] = next[3] = next[j]+1 = 0+1 = 1。
  

• j=3：k = next[j] = 1，p[k] != p[j]（'a' != 'c'），令k = next[k] = next[2] = 0，而p[0] != p[j]（'a' != 'c'），再次匹配失败，k = next[k] = -1，next[j+1] = next[4] = 0。
  

• j=4：k = next[4] = 0，p[0] == p[j] == 'a'，匹配成功，next[j+1] = next[j]+1 = 1。
  

• j=5：k = next[5] = 1，p[1] == p[j] == 'b'，匹配成功，next[j+1] = next[j]+1 = 2。
  

• j=6：k = next[6] = 2，p[2] == p[j] == 'a'，匹配成功，next[j+1] = next[j]+1 = 3。
  

🥕进行匹配

n = strlen(l) = 20
next[]: {-1, 0, 0, 1, 0, 1, 2, 3}
l[]: "abacabacabadabacabae"
p[]: "abacabae"

首先，i = 0, j = 0，从头开始匹配。

进入while循环：
l[i] == p[j] == 'a'，i++, j++。

现在i = 1, j = 1。

l[i] == p[j] == 'b'，i++, j++。

现在i = 2, j = 2。

l[i] == p[j] == 'c'，i++, j++。

现在i = 3, j = 3。

…
i = 6, j = 6时：
l[i] == p[j] == 'b'，i++, j++。

现在i = 7, j = 7。

但是，l[7] != p[7]（'c' != 'e'），进入else，j = next[j]。

j = 7，next[j] = 3。

现在j = 3（相等于p往后移4格）。

下面继续匹配到i = 10, j = 6。

现在i = 11, j = 7，但i[11] = 'd'，j[7] = 'e'，不匹配，故令j = next[j]，现在j = 3（相等于p往后移4格）。

但仍旧l[i] != p[j]（'d' != 'c'），继续令j = next[j]，现在j = next[3] = 1（相等于p往后移2格）。

仍然不匹配（'d' != 'b'），令j = next[j] = 0（相等于p往后移1格）：

仍然不匹配（'d' != 'a'），令j = next[j] = -1，触发第一个if，所以i++, j = 0，从头再来：

下面一直可以匹配，直到j == m（注意最后多加了一个1，所以是m而不是m - 1），退出whie循环，返回p在l中出现的位置i - j = 12。

七、对简洁板子代码的解读

我们打比赛或者考试的时候肯定写的是很简单的代码。

网上广为流传的简洁的代码如下：

int next[MAXN];// 这里将next设为全局变量，也可以在KMPSearch中动态分配内存

void GetNext(const char* p)
{
    int m = strlen(p), k = -1, j = 0; // p的长度，k和j（k=-1是因为next[0]=-1）
    next[0] = -1;
    while(j < m - 1) // j循环从0到m-2
        if(k == -1 || p[k] == p[j]) // 这里合并了两种情况
            next[++j] = ++k; // 更新next[j+1]，且j、k加一
        else k = next[k]; // 套娃
}

int KMPSearch(const char* l, const char* p)
{
    int n = strlen(l), m = strlen(p), i = 0, j = 0; // 设一些变量
    GetNext(p); // 调用GetNext
    while(i < n && j < m)
        if(j == -1 || l[i] == p[j]) // 这里合并了两种情况
            ++i, ++j; // 往下匹配
        else j = next[j]; // 套娃
    if(j == m) return i - j; // 匹配成功
    else return -1; // 匹配失败
}

解读：
⭐️先看GetNext。

与我的代码相比的区别主要是，合并了k == -1和p[k] == p[j]两种情况。

当k == -1时，应该让next[j+1] = 0，这里k++刚好让k = 0。

这也是为什么我们定义next[0] = -1。

当p[k] == p[j]，需要next[j+1] = k+1，然后k++。

这样做略去了k = next[j]的过程，也可以在合适的时候直接j++，不需要外层循环控制j。

⭐️再看KMPSearch。

同样合并了j == -1和l[i] == p[j]两种情况。

其中j == -1时++j使得j = 0；其他的与我的代码差不多。

八、获取模式串所有出现的位置

两种方法：
（一）每次匹配成功后在下一位开始。

这种方法效率稍低，注意只调用一次GetNext即可。

（二）每次匹配成功（j == m）后，令j = next[j]，不break。

此时我们需要知道next[m]，因此GetNext中循环条件改为j <= m。

这里我们给出洛谷P3375 【模板】KMP字符串匹配的代码：

#include 
#include 

using std::cin;
using std::cout;
using std::endl;
using std::strlen;
// 因为std::next与next数组冲突，所以不using namespace std

const int MAXN = 1e6 + 5;

char l[MAXN], p[MAXN];

int next[MAXN];

void GetNext(const char* p)
{
    int m = strlen(p), k = -1, j = 0;
    next[0] = -1;
    while(j < m) // 此处改上限
        if(k == -1 || p[k] == p[j])
            next[++j] = ++k;
        else k = next[k];
}

void FindAll(const char* l, const char* p)
{
    int n = strlen(l), m = strlen(p), i = 0, j = 0;
    GetNext(p);
    while(i < n)
    {
        if(j == -1 || l[i] == p[j])
        {
            ++i, ++j;
            if(j == m)
            {
                cout << i - j + 1 << '\n';
                // 题目要求下标从1开始
                j = next[j];
            }
        }
        else j = next[j];
    }
}

int main()
{
    cin.getline(l, MAXN);
    cin.getline(p, MAXN);
    int n = strlen(l), m = strlen(p);
    if(l[n - 1] == '\r') l[n - 1] = ','-- ;nif
    ([p-m 1 ]== '\r' )[ p-m 1 ]= ',' --; // 数据有奇怪的\r，需要去掉mFindAll
    (
    ,)l; pfor(
    int=1 i ; <=; i ++ m) <<i[ cout ] next<<i' ' ; <<;
    cout return endl0
    ; }
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         +
        
        
         m
        
        
         )
        
       
       
        O(n+m)
       
      
     

九、最终BOSS：时间复杂度的证明

KMP算法的时间复杂度是O(n+m)GetNext O ( m ) O(m) 。

⭐️函数：我的代码中有两层循环，貌似复杂度高于O(m) O ( m ) O(m) 。

但是加起来其实还是O(m)kj的，这与欧拉筛法有异曲同工之妙。

• 我们看对简洁板子代码进行分析。
  

  我们发现，j只有在m增加的时候才会增加，k一定会增加m次，故k = next[k]也增加k次。
  

  而每次 1 1 的套娃过程都至少会让减少1mwhile，减少的次数显然不会超过增加的次数，所以减少的次数不会超过2m次。
  

  因此GetNext循环执行了不超过O(m)次，即 j j 的复杂度为。
  

• 对我的代码分析也可以得出这个结果。
  

  对于一个jk = next[k] f ( j ) f(j) ，设的执行次数为f(j)k 1 1 次（每次至少减少1 f ( j ) ≤ next [ j ] f(j)\le\text{next}[j] ），则f(j)≤next[j]k = next[j] f ( j ) f(j) 。
  

  一开始，进行了f(j)k next [ j ] − f ( j ) \text{next}[j]-f(j) 次套娃后至多为next[j]−f(j) f ( j + 1 ) ≤ next [ j + 1 ] ≤ next [ j ] − f ( j ) + 1 f(j+1)\le\text{next}[j+1]\le\text{next}[j]-f(j)+1 ，所以f(j+1)≤next[j+1]≤next[j]−f(j)+1 f ( m − 1 ) ≤ next [ m − 2 ] − f ( m − 2 ) + 1 ≤ next [ m − 3 ] − f ( m − 3 ) − f ( m − 2 ) + 2 ≤ next [ m − 4 ] − f ( m − 4 ) − f ( m − 3 ) − f ( m − 2 ) + 3 ≤ ⋯ ≤ next [ 0 ] − ∑ j = 0 m − 1 f ( j ) + m − 1 \begin{aligned}f(m-1)&\le\text{next}[m-2]-f(m-2)+1\&\le\text{next}[m-3]-f(m-3)-f(m-2)+2\&\le\text{next}[m-4]-f(m-4)-f(m-3)-f(m-2)+3\&\le\cdots\&\le\text{next}[0]-\sum\limits_{j=0}^{m-1}f(j)+m-1\end{aligned} 。
  

  
  所以f(m−1)​≤next[m−2]−f(m−2)+1≤next[m−3]−f(m−3)−f(m−2)+2≤next[m−4]−f(m−4)−f(m−3)−f(m−2)+3≤⋯≤next[0]−j=0∑m−1​f(j)+m−1​ ∑ j = 0 m − 1 f ( j ) ≤ next [ 0 ] + m − 1 − f ( m − 1 ) ≤ m − 2 \sum\limits_{j=0}^{m-1}f(j)\le\text{next}[0]+m-1-f(m-1)\le m-2 移项得j=0∑m−1​f(j)≤next[0]+m−1−f(m−1)≤m−2 ∑ j = 0 m − 1 f ( j ) = O ( m ) \sum\limits_{j=0}^{m-1}f(j)=O(m) 所以j=0∑m−1​f(j)=O(m) m − 2 m-2 ，即套娃总共最多执行了m−2KMPSearchi次。
  

⭐️j函数：KMP算法在不增加i的情况下不会增加n。

因为j增加了n次，所以j = next[j]至多减少n次，即 O ( n ) O(n) 的套娃不超过次。

因此这部分复杂度为O(n) O ( n + m ) O(n+m) 。

综上，KMP的复杂度为O(n+m)前缀后缀。

答疑

---

🍎Q1：
在图示的情况下，若k = next[j]和0~j-1的长度为前缀（匹配部分为淡绿色），那么会不会出现前缀和j - next[j]的交界处包含前缀的情况呢？（如下图所示）

在这种情况下，如果按我们介绍的往右跳前缀格的方法，不就可能漏了前缀和方框部分对齐的情况吗？

A1：这确实是可能出现的，不过对结果没有影响。

假设真的出现了这种情况，设淡绿色部分=PQP（P、Q是它的子串，方框与黄色部分公共部分是P），模式串=QPR（方框里面是QP，外面是R），红框=S。

则模式串=PQPQPRPQPS。

如果真的在我们所说的地方匹配了的话，上图的0~j-1部分是对应相等的，即RPQ=QPR。

再看模式串的0~j-1部分，取它的一个前缀PQP(QPR)P及后缀PQPRPQP，在前缀中代入QPR=RPQ得PQP(QPR)P=PQP(RPQ)P=后缀，故k = next[j]的next部分有比PQP还长的相等的前缀和后缀，与前缀矛盾。

所以如果真的能匹配，后缀值肯定很大，不会出现问题。

如果不能匹配，跳过这里也没有任何关系。

所以不需要担心这个问题。

再次提醒：next和 s 1 s_1 是可能重叠的~

---

例题解析

数组的应用——洛谷P4391 [BOI2009]Radio Transmission 无线传输
题目大意：一个字符串s1​ s 2 s_2 由s2​ s 1 s_1 不断拼接而成，现在给出s1​ s 2 s_2 的一个子串，求s2​ s 1 = s_1= 的最短长度。

例如，给出s1​=cabcabca s 2 = s_2= ，则s2​=cab 3 3 ，输出3 n = s t r l e n ( s 1 ) n={\rm strlen}(s_1) 。

分析：令n=strlen(s1​) m = s t r l e n ( s 2 ) m={\rm strlen}(s_2) ，m=strlen(s2​) s 1 s_1 。

考虑s1​ s 3 s_3 的尾巴部分s3​ s 2 s_2 是s2​ p = ( n   m o d   m ) p=(n\ {\rm mod}\ m) 的一个子串，其长度为p=(n mod m) s 3 s_3 。

例子中s3​ca s 1 s_1 等于。

又设s1​ N N 是由N s 2 s_2 个s2​ s 3 s_3 和一个s3​ N = 2 N=2 拼接而成（例子中N=2 s 1 s_1 ）。

考虑s1​ n − m n-m 的长度为n−m u u 的前缀u N − 1 N-1 ，其由N−1 s 2 s_2 个s2​ s 3 s_3 和一个s3​ s 1 s_1 拼接而成。

再考虑s1​ n − m n-m 的长度为n−m v v 的前缀v N − 1 N-1 ，也由N−1 s 2 s_2 个s2​ s 3 s_3 和一个s3​ u = v u=v 拼接而成。

所以u=v n e x t [ n ] = n − m {\rm next}[n]=n-m ，next[n]=n−m n − n e x t [ n ] n-{\rm next}[n] 。

所以答案是n−next[n]#include。

AC代码：

#include 
using:: 

; stdusingcin::
; stdusingcout::
; stdusingstrlen::
; stdconstendlint

= 1e6 MAXN + 5 ; char[

] s;MAXNint[
] next;MAXNintmain

( )int;
{
    ; n.
    cin >> nget
    cin();// 略去'\n'. getline
    cin(,)s; MAXN[0
    next]=- 1 ;for(
    int=1 i ; <; i ++ n) iint=
    {
        [ k ] next;iwhile(
        !=-k 1 )if(
            []s==k[ ] s)i[+
            {
                next1i ] =+ 1 k ; break;
                }else
            =
            [ k ] next;kif(
        ==-k 1 )[+ next1i ] =0 ; }<<
    -
    cout [ n ] next<<n; return endl0
    ; }
KMP Algorithm for Pattern Searching - Geeks for Geeks
https://blog.csdn.net/v_JULY_v/article/details/7041827

参考文献

1. Knuth-Morris-Pratt (KMP) algorithm explained（有严谨的数学证明）
2. What is the best & worst time complexity Of KMP algorithm