以下均搬运自花姐姐的博客

闲话：$KMP$作为一个经典的字符串算法，自然值得$OIer$学习，但往往因其实现难、不常考，导致$OIer$不想学（话说这不是人之常情吗），今天，让我们来解决这一毒瘤，改变我们遇字符串就炸的现象吧！

一、何谓模式串匹配

模式串匹配，就是给定一个需要处理的文本串（理论上应该很长）和一个需要在文本串中搜索的模式串（理论上长度应该远小于文本串），查询在该文本串中，给出的模式串的出现有无、次数、位置等。

这就相当于$OJ$上判断程序对错的过程，$OJ$通过匹配每一个字符来判断输出结果的正误，也算是一种模式串匹配。

二、KMP算法的核心思想

首先，我们来了解一下$KMP$算法的由来。度娘说

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。
因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

然而，这些伟人我一个也不认识，但这并不妨碍它成为一个伟大的算法。

首先，让我们来分析一下我们朴素算法被$T$飞的原因：我们用低效的枚举匹配文本串，导致在最坏情况下该算法（好像也不能叫算法）退化成O（文本串长度*匹配串长度），其实也比较好卡，如以下数据

文本串：aaaaaaaaaaa......aaaaaaaaab (其中有1e6个a)
模式串：aaaaaaaaaaa......aaaaaaaaab (其中有5e5个a)

那么，我们要执行$2.5e6$次计算，会直接导致超时(TLE)

既然如此，当然轮到我们KMP算法闪亮登场了！

KMP 的精髓在于，对于每次失配之后，我都不会从头重新开始枚举，而是根据我已经得知的数据，从“某个特定的位置”开始匹配；而对于模式串的每一位，都有唯一的“特定变化位置”，这个在失配之后的特定变化位置可以帮助我们利用已有的数据不用从头匹配，从而节约时间。

举个栗子

文本串:abaabab
模式串:aba

正常的算法（暴力）会在第三个字符之后重新开始匹配，但让我们来看一看KMP算法的运行过程

文本串:abaabab
模式串:   	aba

所以，KMP在每次失配之后就可以跳回之前的某一位，在从该位开始新的一轮匹配。

注意：
1.一般使用模式串来匹配失配数组。

2.匹配位置的确定。

$str1$ 中，对于每一位 $str1(i) $,它的 $kmp$ 数组应当是记录一个位置 $j, j≤i$并且满足 $str1(i)=str1(j) $并且在$j!=1 $时理应满足$str1(1)$至 $ str1(j−1) $ 分别与 $str1(i−j+1)~str1(i−1) $ 的每一位相等。

对于2,我们可以用前缀和后缀的思想来理解

模式串:abcdabc
前缀:a,ab,abc,abcd,abcda,abcdab,abcdabc
后缀:c,bc,abc,dabc,cdabc,bcdabc,abcdabc

用$kmp$数组记录到它为止的模式串前缀的真前缀和真后缀最大相同的位置（注意，这个地方没有写错，是真的有嵌套qwq）。

如上面例子中，前缀和后缀的第三项相同，所以$kmp[7]=3$;

三、讲了这么多，直接上代码吧

1.$string$类型的$KMP$

int nxt[MAXN];
void getnext(string t){
	int j=0,k=-1;
	nxt[0]=-1;
	while(j<t.size()){
		if(k==-1||t[j]==t[k]) nxt[++j]=++k;
        //1.当k=-1时，肯定到顶了，不能再回溯，所以直接赋值
        //2.当t[j]==t[k]时，这个下标的nxt值就是上一个下标的值加1
		else k=nxt[k];//如果还没有找到，就返回上一个可回溯的下标再找
	}
}

void KMP(string s,string t){
	int i=0,j=0;
	while(i<s.size()){
		if(j==-1||s[i]==t[j]){++i;++j;}
        //1.当j=-1时，说明到了边界，把文本串的指针加1,再重新开始新一轮匹配
        //2.当s[i]==t[j]时，说明匹配到了，那就指针往后移，看下一位能否匹配
		else j=nxt[j];//如果没有到边界又没有匹配到，就回溯看能否重新匹配
		if(j==t.size()){printf("%lld\n",i-t.size()+1);j=nxt[j];}
        //当j==t.size()时，说明已经完全匹配了，输出答案，并回溯匹配其他位置上的合法答案
        //对输出结果的解释:i表示到下标为i的位置时两串完全匹配，减去（t.size()-1）就是减去模式串的长度，结果就是匹配的起始位置
	}	
}

2.$char$数组类型的$KMP$

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define int long long
#define R register
using namespace std;
//---------------------初始函数-------------------------------
il int read(){
	R int x=0;R bool f=0;R char ch=gc();
	while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
	return f?-x:x;
}

il int max(int a,int b) {return a>b?a:b;}

il int min(int a,int b) {return a<b?a:b;}


//---------------------初始函数-------------------------------

const int MAXN=1e6+10;
char s1[MAXN],s2[MAXN];
int kmp[MAXN];

signed main(){
	scanf("%s%s",s1+1,s2+1);
    //细节：s1+1表示从下标为一的位置开始读入，方便之后的操作
	int lens1=strlen(s1+1),lens2=strlen(s2+1);
    //因为char不像string一样有很多自带函数，所以要用<cstring>库中的函数求长度
	kmp[0]=kmp[1]=0;//初始化
	for(R int j=1,k=0;j<lens2;++j){
		while(k&&s2[j+1]!=s2[k+1]) k=kmp[k];
        //当k>0且s2[j+1]!=s2[k+1]时，说明既没有到边界又没有匹配到，就回溯看能否重新匹配
		if(s2[j+1]==s2[k+1]) ++k;
        //由上面的while循环可知，现在的k一定是匹配的，所以我们只需要判断这一位能否比上一位多匹配一个字符
		kmp[j+1]=k;//赋值这一位最多能匹配的字符
	}
	for(R int j=0,k=0;j<lens1;++j){
		while(k&&s1[j+1]!=s2[k+1]) k=kmp[k];
        //当k>0且s2[j+1]!=s2[k+1]时，说明既没有到边界又没有匹配到，就回溯看能否重新匹配
		if(s1[j+1]==s2[k+1]) ++k;
        //由上面的while循环可知，现在的k一定是匹配的，所以我们只需要判断这一位能否比上一位多匹配一个字符
		if(k==lens2){printf("%lld\n",j+1-lens2+1);k=kmp[k];}
        //当k==lens2时，说明已经完全匹配了，输出答案，并回溯匹配其他位置上的合法答案
        //对输出结果的解释:j表示到下标为j+1的位置时两串完全匹配，减去（lens2-1）就是减去模式串的长度，结果就是匹配的起始位置        
	}
	for(R int i=1;i<=lens2;++i) printf("%lld ",kmp[i]);
	return 0;
}

好了，$KMP$的基本内容到此结束，在加一个时间复杂度分析就完美了。以下引用$rqy$的话：

每次位置指针$i++$时，失配指针$j$至多增加一次，所以$j$至多增加$len$次，从而至多减少$len$次，所以就是$\Theta$（$len_N$+$len_M$)=$\Theta$(N+M)。

其实我们也可以发现，$ KMP $算法之所以快，不仅仅由于它的失配处理方案，更重要的是利用前缀后缀的特性，从不会反反复复地找，我们可以看到代码里对于匹配只有一重循环，也就是说 $KMP$ 算法具有一种“最优历史处理”的性质，而这种性质也是基于$ KMP $的核心思想的。

另外一篇讲的比较好的博客

OI-wiki上别人推荐的博客

完结撒花了

没想到吧，我又回来了！

作为一名合格的$OIer$，我们当然要讲练结合，打出一套合击拳，才能更好的巩固我们对$KMP$算法的理解。

1.来一道裸的$KMP$的题（题解）

2.这才是$KMP$的板子（题解）

3.对$kmp$数组新定义（当提升思维的题做）（题解）（我的代码）

差一点自主做出的紫题，还是要多注意码代码时的细节

4.$KMP$+线性$DP$（讲的特别详细的题解）（我的代码）

5.终极难题：$KMP$+$DP$+矩阵乘法

啊，这题是真的写不动，先咕着吧。

原来KMP还可以求循环子串，学到了学到了，再扔几道例题吧！

1.求最短循环子串（学习$KMP$求循环子串的不错的博客+题解）（我的代码）

2.求循环子串数量（讲的不错的题解）（我的代码）

3.求最长循环子串长度和（题解）（我的代码）

(终于上了一道要脑子的题，要用类似并查集路径压缩的优化)