很久之前学的了。
做个笔记回忆一下：
kmp
朴素比对字符串
所谓字符串匹配，是这样一种问题：“字符串 T 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；T 称为模式串。如在字符串s abcabcabcabd 中找到子串T abcabd :
先设两个指针i、j，i表示S的指针，j表示T的指针
i=j=0
↓(i)
abcabcabcabd
abcabd
↑(j)
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
.
.
.
↓
abcabcabcabd
abcabd
↑
c≠d，回溯(i=1,j=0)
↓
abcabcabcabd
abcabd
↑
b≠a，回溯(i=2,j=0)
.
.
.
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
.
.
.
↓
abcabcabcabd
abcabd
↑
匹配成功，找到模式串(print(i))
优化
上面的复杂度是 O(nm) ，为什么这么多，发现是回溯花费时间过多。我们合理的希望是i不回溯，即：
先设两个指针i、j，i表示S的指针，j表示T的指针
i=j=0
↓(i)
abcabcabcabd
abcabd
↑(j)
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
.
.
.
↓
abcabcabcabd
abcabd
↑
c≠d，i不回溯(j=2)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
↓
abcabcabcabd
abcabd
↑
a≠d，i不回溯(j=2)
↓
abcabcabcabd
abcabd
↑
匹配成功，移动指针(i++,j++)
.
.
.
↓
abcabcabcabd
abcabd
↑
匹配成功，找到模式串(print(i))
全程i不会减少
nxt数组
我们假设知道一个叫做nxt的数组，代表下一个j，当匹配失败时就可以 j=nxt[j] 来防止i的回溯。那么我们可以快速算出他的子串，如下代码：
int KMP(){
for(int i=0,j=0;i<n;i++){
while(j>0 && str[i]!=pnt[j]){
j=nxt[j-1]; // 为什么是 nxt[j-1]，这里埋一个伏笔
}
if(str[i]==pnt[j]){
j++; // 匹配成功
}
if(j==m){ // 匹配成功
return i-j+1;
}
}
return -1;
}
nxt数组是什么
nxt代表重复真子集长度，和回文串差不多，但不是回文串。区别
回文串：abccba
重复真子集：abcabc
欸，那么我们可以看出当已经有abc不匹配：
↓
abcabdabcabc
abcabc
↑
我们可以快速跳到重复真子集中与他重复的部分：
↓
abcabdabcabc
abcabc
↑(虽然c也不等于d)
我们nxt储存的就是与它重复的这部分的位置。以 abcababdabc 为例：
a:0（因为是真子集，不包括自身）
ab:0
abc:0
abca:1
abcab:2
abcaba:1
abcabab:2
abcababd:0
abcababda:1
abcababdab:2
abcababdabc:3
那么我们会发现，他们重复这部分的下标（以0开始）刚好就是重复真子集长度：
abcab为例，abcab的重复真子集长度为2，而且ab也是重复的，所以我们只需要匹配下标为2的c即可。j=nxt[5]
计算nxt数组
我们可以用递推的思想，先设有nxt[0]=0（必然的），然后设有快指针i=1,慢指针j=0，刚好，我们会发现重复部分的长度也是j的值。
对于匹配成功，则j++
对于匹配失败，则从上一位nxt中找到重复部分回溯j。
代码如下：
void makeNext(){
nxt[0]=0;
for(int i=1,j=0;i<m;i++){
while(j>0 && pnt[i]!=pnt[j]){
j=nxt[j-1]; // 因为nxt表示重复部分的下标，我们可以回溯回去
}
if(pnt[i]==pnt[j]){
j++;
}
nxt[i]=j;
}
}
为什么kmp代码中j=nxt[j-1]
是指kmp()中的而不是makeNext()中的，因为第j位和第i位已经不匹配了，j-1位和i-1位才是匹配的，所以用j=nxt[j-1]
代码：
#include<cstdio>
#include<cstring>
#include<string>
char str[1010],pnt[1010];
int n,m;
int nxt[1010];
void makeNext(){
nxt[0]=0;
for(int i=1,j=0;i<m;i++){
while(j>0 && pnt[i]!=pnt[j]){
j=nxt[j-1];
}
if(pnt[i]==pnt[j]){
j++;
}
nxt[i]=j;
}
}
int KMP(){
for(int i=0,j=0;i<n;i++){
while(j>0 && str[i]!=pnt[j]){
j=nxt[j-1];
}
if(str[i]==pnt[j]){
j++;
}
if(j==m){
return i-j+1;
}
}
return -1;
}
int main(){
scanf("%s %s",str,pnt);
n=strlen(str);
m=strlen(pnt);
makeNext();
printf("%d",KMP());
}