蒟蒻学习了(KMP)算法之后的一点总结
目录：
-
初识(KMP)算法
-
(KMP)算法的思想
-
$KMP $算法的程序实现
-
(KMP)算法的板子题
-
总结
(1.) 初识(KMP)算法
首先，什么是(KMP)算法？
(KMP)算法是用来处理字符串匹配问题的。也就是给你两个字符串，你需要回答：(B)串是否为(A)串的子串？（也就是(A)串是否包含(B)串）
举个例子：
字符串(A=GCAKIOIIMOICOIBO)，字符串(B=GCAKIOI)，字符串(C=GCtqlorz)
我们说(B)是(A)的子串，而不能说(C)是(A)的子串
一般来说，解决这类问题用的方法是暴力枚举：
枚举从(A)串的什么位置起开始于(B)串匹配，然后验证是否完全匹配，假设(A)串长度为(n)，(B)串长度为(m)，那么这个算法的复杂度较为可观，是(O(nm))。
但是······
也有例外，比如，当(A=aaaaaaaaaaaaaaaaab)，(B=aaaaaaab)时，枚举方法的复杂度就不能能够满足程序执行的需求。
所以有什么解决方法吗？
当然有，(KMP)算法就是用来解决这个问题的，这个算法可以保证在最坏情况下，时间复杂度仍能为(O(n))。当然，在这里(mleq n)。
(2.) (KMP)算法的思想
叨叨了这么多，到底(KMP)算法是啥样的呢？
我们假设(A=gcgcgcggcgcak)，(B=gcgcgak)，接下来我们根据算法流程手推一下(KMP)算法
算法思路是这样的：
定义两个变量(i)和(j)，表示(A[i-j+1···i])与(B[1···j])完全相等。也就是说，(i)是不断增加的，随着(i)的变化，(j)也不断地变化。且满足以(A[i])结尾的长度为(i)的字符串正好匹配(B)串的前(j)个字符。
现在，我们需要检验(A[i+1])和(B[j+1])的关系。很显然，如果(A[i+1]=B[j+1])，(i)和(j)各加一，表示继续向前检验；如果(A[i+1] eq B[j+1])，(KMP)算法的思路是调整(j)的位置，也就是减小(j)的值，使得(A[i-j+1···i])与(B[1···j])保持匹配并且继续程序。当(j=m)时，(B)就是(A)的子串啦！
手推第一步：
根据上面的流程，我们直接跳到(i=j=5)的情况上
(i) 1 2 3 4 5 6 7 8 9 ··· (A) (g) (c) (g) (c) (g) (c) (g) (g) (c) ··· (B) (g) (c) (g) (c) (g) (a) (k) ··· ··· ··· (j) 1 2 3 4 5 6 7 此时，(A[6] eq B[6])，也就是说，此时(j)不能等于5了，我们要把它改成一个更小的值(j')，于是我们想到将(j)改为3，也就是能使两个字符串继续匹配的最大(j)值。那么我们就需要预处理出一个数组(p[i])表示处理到(j)而(j+1)不能匹配时要转移到的最大(j)值。
手推第二步：
继续程序，我们来到了(i=7,j=5)的情况上
(i) 1 2 3 4 5 6 7 8 9 ··· (A) (g) (c) (g) (c) (g) (c) (g) (g) (c) ··· (B) (g) (c) (g) (c) (g) (a) (k) ··· (j) 1 2 3 4 5 6 7 此时，(A[8] eq B[6])，我们要继续程序，(p[5]=3)，所以新的(j)值为3；
手推第三步：
继续程序，我们来到了(i=7,j=3)的情况上
(i) 1 2 3 4 5 6 7 8 9 ··· (A) (g) (c) (g) (c) (g) (c) (g) (g) (c) ··· (B) (g) (c) (g) (c) (g) (j) 1 2 3 4 5 此时，(A[8] eq B[4])，我们要继续程序，(p[3]=1)，所以新的(j)值为1；
手推第四步：
继续程序，我们来到了(i=7,j=1)的情况上···
限于篇幅，下面的部分大家自己手推一下，我就不往上写了
(3.) (KMP)算法的程序实现
解决了程序的流程问题，接下来我们看一下程序的核心部分，其实程序的实现并不是很难，只要理解了程序的流 程，其他都好说（其实也好背）
先是(KMP)算法的核心部分，即处理字符串匹配的部分
j=0;//j的值最初为0，即从0开始匹配A串
for(int i=0;i<n;++i)//将A串从头扫到尾
{
while(j>0&&B[j+1]!=A[i+1])//如果已经进行匹配并且B[j+1]不能与A[i+1]进行匹配
j=p[j];//令当前的j值为p[j]，p[j]的定义前面有讲到
if(B[j+1]==A[i+1])//如果能继续匹配下去
++j;//继续下一个匹配
if(j==m)//如果整个B串完全匹配
{
printf("%d
",i+1-m+1);//输出B串所在的位置（不要问我为什么是i+1-m+1)
j=p[j];//继续进行匹配，因为可能还有子串被包含
}
}
接下来是(KMP)算法的另一个重要环节——处理(p)数组
我们可以发现，处理(p)数组的代码与处理字符串匹配的代码很相像（甚至只背一个部分就可以啦）。其实，(p)数组的处理就是一个(B)串自我匹配的过程，所以与处理两个字符串匹配的代码蜜汁相像
p[1]=0;//如果B串从第一个字符开始就不能匹配，那么就将B串向右移一位
for(int i=1;i<m;++i)//将B串从头扫到尾（注意这里的从头扫到尾并不是从0开始，而是从1开始，因为p数组的处理是B串的自我匹配。如果从1开始，那么每一个字符都会匹配。这样一来就无法求出p数组，从而影响整个程序）
{
while(j>0&&B[j+1]!=B[i+1]) //如果已经进行匹配并且B[j+1]不能与B[i+1]进行匹配
j=p[j];//令当前的j值为p[j]
if(B[j+1]==B[i+1]) //如果能继续匹配
++j;//将进行匹配的B串向右移一位
p[i+1]=j;//这里是最重要的，就是说当前的第i个字符要转移到上一个能够继续匹配的地方，也是上一个能自我匹配的地方
}
(4.) (KMP)算法的板子题
题目描述：
给出两个字符串(s_1)和(s_2)，其中(s_2)为(s_1)的子串，求出(s_2)在(s_1)中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组(next)。
（如果你不知道这是什么意思也不要问，去百度搜([KMP])学习一下就知道了。）
题目分析：
就是(KMP)的板子题，这里面的(next)数组就是我们费尽心机求的(p)数组，那么在程序结束时直接输出(p)数组就好了(qwq)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char A[1000010],B[1000010];
int p[1000010];//p数组要开的和B数组一样大
int m,n,j;
int main()
{
scanf("%s",A+1);//A+1表示从1开始读入A串，下同
scanf("%s",B+1);
n=strlen(A+1);
m=strlen(B+1);
p[1]=0;
for(int i=1;i<m;++i)//处理p数组
{
while(j>0&&B[j+1]!=B[i+1]) j=p[j];
if(B[j+1]==B[i+1]) ++j;
p[i+1]=j;
}
j=0;//一定别忘记将j值清零
for(int i=0;i<n;++i)//字符串匹配
{
while(j>0&&B[j+1]!=A[i+1]) j=p[j];
if(B[j+1]==A[i+1]) ++j;
if(j==m)
{
printf("%d
",i+1-m+1);
j=p[j];
}
}
for(int i=1;i<=m;++i) printf("%d ",p[i]);//输出p数组
return 0;//恭喜你通过了这道题！！！
}
(5.) 总结
其实(KMP)算法并不是很难，但是程序中的小细节特别多。总之就是一句话，还得练。