题目就是补全代码.
此处主要简单证明且叙述kmp原理.
prefix[j] 存放当模式串匹配到j，位置与主串位置i，存在s[i]!=p[j]时，进行性下次操作
只需要使得下次j=prefix[j],在与i,进行匹配.
因此prefix[i]数组中存放这样的整数k
使得有模式串
p[1 to k-1] 与 p[(i-1)-(k-1)+1 to (i-1)] 完全匹配时的k
如最上面图中的prefix[7]=4;
因为p[1 to 3] 与 p[(7-1)-(4-1)+1 to (7-1)] (即p[4 to 6])完全相等
因此prefix[7]=4,
下次j=7;失败时依据上图原理j=prefix[j],在进行s[7] 与 p[4]的匹配即可.
换句话说prefix[j]中存放的是p j-1的后缀串 与p j-1的前缀串最大匹配串长
此处定义
串s ,不是s自身的子串，因此根不能为自己的前缀串或后缀串
prefix[]
数组的求法可以用朴素的方法来求
int pn,int i,int k;
for(i=1;i
for(k=1;k
如果p[1 to k] 与 p[k to pn]相等时
if(ismatch(p,1,k,p,k,pn)))
prefix[i]=max(prefix[i],k);
}
}
或者根据如下事实写出代码
如果已经有
p[1 to k] 与 p[i-k+1 to i] 相等
此时如果
p[k+1]等于p[i+1]
时prefix[i+2]=k+1;
并且i++,j++;进行下次比较,仍存在p[1 to k] 与 p[i-k+1 to i+1]相等.//有归纳法可得。
如果不相等
另j=prefix[j]，prefix[j]的意义,
则存在 p[1 to prefix[j]] 等于 p[(j-1) - prefix[j] +1 to (j-1)]相等非常重要
因此另j=prefix[j];进行下次比较.
到此为止kmp思路就说明完毕了
下面是代码（参照数据结构）
#include <cstring>
#include <iostream>
using namespace std;
int prefix[100]={0};
int Prefix(char p[]){
int i,j=0;
prefix[i=1]=0;
while(i<p[0]){
if(j==0||p[i]==p[j]){
i++;
j++;
prefix[i]=j;
}else
j=prefix[j];
}
}
int Kmp(char s[100],int pos,char p[100]){
int i=pos;
int j=1;
Prefix(p);
while(i<=s[0]&&j<=p[0]){
if(j==0||s[i]==p[j]){
i++;
j++;
}else{
j=prefix[j];
}
}
if(j>p[0])
return i-p[0];
return -1;
}
int main(){
char s[100];
char p[100];
cin>> s+1 >> p+1 ;
s[0]=strlen(s+1);
p[0]=strlen(p+1);
cout<< Kmp(s,1,p)<<endl;
return 0;
}