【KMP】【字符串】KMP字符串匹配算法 学习笔记
一、简介
KMP是由Knuth、Morris和Prat发明的字符串匹配算法，它的时间复杂度是均摊\(O(n+m)\)。其实用Hash也可以做到线性，只不过Hash存在极其微小的难以避免的冲突。于是就有了KMP。
KMP算法用作模式串匹配，可以找到一个长为\(m\)的模式串在一个长为\(n\)的主串中出现的次数和位置。
二、朴素算法(\(O(nm)\))
实际上是枚举模式串在主串中出现的位置，然后一一比对，出现错误就停止，移动到下一位。连续匹配成功\(m\)次就说明模式串在主串中出现了。
其实\(O(nm)\)是一个比较宽的上界，随机数据远没有这么慢。不过给出主串S="aaaaaaaaaaa"，模式串T="aaab"，就得每次匹配到最后才知道挂掉了。那么我们既然已经知道这样会挂掉，为什么还要重复匹配呢？这就是KMP要解决的问题。
三、KMP算法
0.注意事项
KMP算法中，字符数组下标是从1开始而不是0，这样会比较方便，在匹配的时候直接调用nxt数组就不用-1了，而且很直观。
1.nxt数组(next)
nxt数组是KMP算法的核心。
nxt数组nxt[i]中存的是后缀字符与前缀字符相同的个数，且后缀字符不是前缀字符，也就是不能完全匹配自己。
对于ababcab而言，它的nxt数组是
| nxt[1] | nxt[2] | nxt[3] | nxt[4] | nxt[5] | nxt[6] | nxt[7] |
| a | ab | aba | abab | ababc | ababca | ababcab |
| 0 | 0 | 1 | 2 | 0 | 1 | 2 |
| 没有后缀与前缀相同 | 没有后缀与前缀相同 | 前缀”a”=后缀”a” |
前缀”ab”=后缀”ab” 注意不能完全匹配自己 |
没有后缀与前缀相同(失配直接=0) | 前缀”a”=后缀”a” | 前缀”ab”=后缀”ab” |
看上去很简单。但是它怎么求呢？当然，如果递推掌握的比较好，可以知道，如果T[i+1]==T[nxt[i]+1]，那nxt[i+1]=nxt[i]+1。而失配了怎么办，是我们接下来要解决的问题。
2.nxt数组的作用
在上面我们提到了，KMP算法是减少了朴素算法的重复匹配，均摊下来每个字符只匹配了一次。在上面的表格中，我们看到了nxt数组处理出了模式串后缀与前缀匹配数。当我们用模式串匹配主串，在后缀失配时，在模式串里与后缀相同的就是我们预处理出的前缀了，因此我们只需要把模式串前缀挪到现在的位置来即可。这时我们会发现，中间可能跳过很多没有用，也就是安排匹配不上的状态，这就是KMP的优化。
3.nxt失配的求法
可以看出，求nxt数组，就是在用模式串匹配自己，且不匹配第一位。当我们发现T[i+1]与T[nxt[i]+1]失配时，比nxt[i]要次一点但是仍然与T[i]所在后缀相同的前缀就是nxt[nxt[i]]了。就是我们相当于退而求其次，“贪心地”按长度从大到小找一个最能匹配上后缀的前缀。
匹配不到的情况
比如说
ababababc
↑
如果匹配到第8+1位时失配了，这时就去找第nxt[8]+1位，（nxt[8]=6）也就是第6+1位。此时发现还是不行，继续找第nxt[6]+1位……直到找到nxt[1]=0，退出循环，再看看第一位是否匹配，如果匹配，nxt[9]=1，否则nxt[9]=0。
重新匹配到的情况
abcaba
↑
这里匹配到第5+1位发现失配，去找nxt[5]+1=2+1，仍然不行，但是nxt[2]=0了，此时退出循环，发现T[1]=T[6]，所以nxt[6]=1。
其实情况还有很多很多种，这里只是列举了几种，想让nxt数组的求法变得更加形象一些。
四、KMP代码
#include<cstdio>
#include<cstring>
char s[1000100];
char t[1000100];
int nxt[1000100];
int f[1000100];
int main()
{
scanf("%s",s+1);
scanf("%s",t+1);
int n=strlen(s+1);
int m=strlen(t+1);
for(int i=2,j=0;i<=m;++i)
{
while(j&&t[i]!=t[j+1])
j=nxt[j];
if(t[j+1]==t[i])
++j;
nxt[i]=j;
}
for(int i=1,j=0;i<=n;++i)
{
while(j&&(j==m||s[i]!=t[j+1]))
j=nxt[j];
if(t[j+1]==s[i])
++j;
f[i]=j;
if(f[i]==m)
printf("%d\n",i-m+1);
}
for(int i=1;i<=m;++i)
printf("%d ",nxt[i]);
return 0;
}