KMP算法
2021-05-04 22:27
标签：oid mic nbsp turn load 快速 alt png ext 1.目的 在主串中快速，快速，快速地找到目标串 2.求解next数组 3.KMP算法 4.改进 对KMP算法的改进主要体现在对Next数组的改进上 这里假设Pd,Pc,Pb都与Pj相同，Pa与Pj不同。 1.当Pk不等于Pj时，nextval[k]=next[k]=j; 2.当PK等于Pj时候，nextval[k]=nextval[next[k]]=nextval[j]; KMP算法 标签：oid mic nbsp turn load 快速 alt png ext 原文地址：https://www.cnblogs.com/jcahsy/p/13194325.html
void getNext(StrNonfix substr,int next[]){
int j=1,t=0;
next[1]=0;
while(jsubstr.length){
if(t==0||substr.ch[j] == substr.ch[t]){
next[j+1]=t+1;
++t;
++j;
}else{
t=next[t];
}
}
}
int KMP(StrNonfix str,StrNonfix substr,int next[]){
int i=1,j=1;
while(isubstr.length){
if(j==0||str.ch[i] == substr.ch[j]){
++i;
++j;
}else{
j=next[j];
}
}
//模式串在主串中的初始位置
if(j>substr.length){
return i-substr.length;
}else{
return 0;
}
}
void getNextval(StrNonfix substr,int nextval[]){
int j=1,t=0;
nextval[1]=0;
while(jsubstr.length){
if(t==0||substr.ch[j] == substr.ch[t]){
if(substr.ch[j+1] !=substr.ch[t+1]){
nextval[j+1]=t+1;
}else{
nextval[j+1]=nextval[t+1];
}
++t;
++j;
}else{
t=nextval[t];
}
}
}