初学者详细解读KMP
题目描述
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串S。
输出格式
共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。
样例
输入
3
aba
5
ababa
输出
0 2
算法1
(暴力枚举)
s[N]指的是模板串(短的),p[M]指的是模式串(长的)。
C++ 代码
for(int i=1;i<=n;i++)
{
bool flag=true;
for(int j=1;j<m;j++)
if(s[i+j-1]!=p[j])
{
flag=false;
break;
}
}
算法2
KMP算法很抽象很难理解,但是只要抓住本质,是找相同字符串的位置,进行匹配,而next数组也是。以下是我手动模拟的关于本题样例的图解。
首先明确两点,第一模式串[ababa],第二模板串[aba]。
关于next数组的计算
同样的kmp,区别就是关于next数组是本模式串内的kmp匹配。先总体讲一下,具体代码实现就是从2开始不断跟前面的数组内的字符比较,看对称相等的字符有多少个。
代码详细解读:
while(j&&p[i]!=p[j+1])j=ne[j];
本条代码意思就是前后对称的字符不相等,没看对眼,j指针所指的值就指向next数组存储的那个值。
简单来说:失配就后退。
if(p[i]==p[j+1]) j++;
本条代码很好理解吧,就是看前后对称的地方有几个相同的,就加几次j,然后存入next。
关于kmp匹配
套路跟上面是一样的,i指针指向模式串,j指针指向模板串。不断的比较不断的移动,如果失配就寻next数组里面所指向的那个值,也就是后退到前缀相同的位置。
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010,M=1000010;
int n,m;
//p[N]指的是模板串(短的),s[M]指的是模式串(长的)。
char p[N],s[M];
int ne[N];//next数组
int main()
{
cin>>n>>p+1>>m>>s+1;
//求next数组过程
for(int i=2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
//kmp匹配过程
for(int i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=p[j+1])j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n)
{
printf("%d ",i-n);
j=ne[j];
}
}
return 0;
}
例子很细节