KMP学习笔记
小柯
2019-10-31 23:14:47
# 解决问题
字符串匹配问题(不限于字符串):
> 一个串是否是另一个串的子串
# 朴素解法
暴力求解(如下)
```
for(i＜=len1){
t=i;
j=1;
while(s1[i]==s2[j]&&j<=len2)i++,j++;
if(j==len2)return true;
i=t+1;
}
```
显然，时间复杂度为$O(len1*len2)$。
所以，我们需要一个更优的算法。
# 优化算法
我们发现，我们在比较两个串时，内层循环会得到一些相等的区间，但终点不等，所以，我们考虑利用这个信息。
■■■■■□□□□□■□■
■■■■■□□□□□■□□
^$\color{white}{yyyyyy}$相同的$\color{white}{yyyyyy}$^
因为我们一旦发现两个不等，i，j就要回到原来的位置，但是前面相等的相当于直接抛弃掉了，所以此时考虑在让i不动，让j跳到一个合适的位置，使得s1串的i-j+1~i和s2串的1~j是相等的。
■□■□□■□■■□■□■□
$\color{white}{yyyyyyyyyyyy}$i
■□■□□■□■□
$\color{white}{yyyyyyyyyyyy}$j
不等了
■□■□□■□■■□■□■□
$\color{white}{yyyyyyyyyyyy}$i
■□■□□■□■□
$\color{white}{yyyy}$j
跳转
那么问题来了，跳到那儿最合适呢?
答案揭晓:s2串1~j的最长相等的前缀后缀的长度。听上去很复杂对不对?我来解释一下:
■□■□□□□■□■□
如上，该串的最长相等前缀后缀就是1~4和8~11，都是“■□■□”。
最后，设pre[i]表示s2串1~i的最长前缀后缀长度，如何求pre[i]呢?实际上，这仍是一个KMP，即pre[1]=0，后面的用s2的全部作S2用s2除了第一个作S1，当j成功到一个合适的位置时，pre[i]=j然后i++即可。
```
for(int i=1,j=0;i<m;i++){
while(b[i]!=b[j]&&j!=0)j=pre[j-1];
if(b[i]==b[j])j++;
pre[i]=j;
}
```
# 代码
KMP模板题代码:
```
#include<iostream>
#include<string>
using namespace std;
int n,m;
int pre[100000005];
string a,b;
void KMP(string a,string b){
for(int i=1,j=0;i<m;i++){
while(b[i]!=b[j]&&j!=0)j=pre[j-1];
if(b[i]==b[j])j++;
pre[i]=j;
}
for(int i=0,j=0;i<n;i++){
while(a[i]!=b[j]&&j!=0)j=pre[j-1];
if(a[i]==b[j])j++;
if(j==m)cout<<i-m+2<<endl,j=0,i=i-m+2;
}
}
int main(){
cin>>a>>b;
n=a.size(),m=b.size();
KMP(a,b);
for(int i=0;i<m;i++)cout<<pre[i]<<" ";
return 0;
}
```