前言：

到底什么是kmp呢？本人认为kmp的优势在于根据之前的信息来快速更新现在的信息，从而提高时间的效率（类似于记忆化搜索？）在此默认大家都会kmp。

主要用处：

一.字符串匹配

代码：

#include<bits/stdc++.h>

#define maxn 1000001

using namespace std;

int kmp[maxn];

char a[maxn],b[maxn];

int la,lb;

int j;

int main()

{

    cin>>a+1>>b+1;

    la=strlen(a+1);

    lb=strlen(b+1);

    j=0;

    kmp[1]=0;

    for(int i=2;i<=lb;i++)

    {

     while(j && b[j+1]!=b[i]) j=kmp[j];

     if(b[j+1]==b[i]) j++;

     kmp[i]=j;

}

j=0;

for(int i=1;i<=la;i++)

{

while(j && b[j+1]!=a[i]) j=kmp[j];

if(b[j+1]==a[i]) j++;

if(j==lb)

{

cout<<i-lb+1<<endl;

j=kmp[j];

}

}

for(int i=1;i<=lb;i++) cout<<kmp[i]<<' ';

    return 0;

}

　　

重点：kmp[i]数组求的即为i位置匹配失败时往前跳的花费最小位置，即模式串i位置前与第一位后的最长公共子串。

例：abaabaa

如果此时匹配失败位置6，则此时直接将指针指向3号，因为1-2号=4-5号，所以既然已经匹配到了第6号说明此时匹配串匹配失败的位置前2个=模式串4-5=模式串1-2号，所以下次重新匹配直接从3号开始，不必再从1号开始，大大节约了时间，此为此算法之精髓。

时间复杂度：O(N)

二.4391(luogu)最小循环子串

给你一个字符串 s1​，它是由某个字符串 s2​ 不断自我连接形成的。但是字符串 s2​ 是不确定的，现在只想知道它的最短长度是多少。

Eg:cabcabca

Ans:cab

题解：答案即为l-kmp[l=s.size()];

证明：

(图在原稿中，无法上传，此处略去，如果需要可私信作者)

绿色为ans,将字符串等量分段，由kmp数组的特性得知则黄色1=绿色2=黄色2=红色1=红色2=蓝色1=蓝色2=草绿色1（数字为排数），则此时只用证明绿色前一半部分包含灰色，灰色2=草绿色前一部分=绿色前一部分，则得证。

三：2375（luogu）

给一个字符串，求每一个位置的公共前后缀且满足前后缀不交叉的数量。

题解：

先求出num1数组表示每个位置交叉的前后缀数量，num1即为一直跳nxt直至nxt=0时的次数（注意前后缀既不能少前面也不能少后面，和回文串不要搞混了，一个公共前后缀不包含别的前后缀，具有唯一性），即可在求Kmp时递推求之。接着每一个位置i的ans即为满足j=while(nxt[i]),(j<<1)<=i的num[j]。

这个题对kmp数组的意义考察的较好，做完这个题，应该会对kmp有更高的认识。

总结

kmp算法主要用于字符串单匹配，前后缀处理一些场景中，时间复杂度也相对可观，代码量较小，但遇到多匹配时，只能上AC自动机了，这可能有树状数组和线段树的意味？