详细解说kmp,第五届蓝桥杯决赛第三题
题目就是补全代码. 此处主要简单证明且叙述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; }题目就是补全代码. 此处主要简单证明且叙述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
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)<