目标:掌握kmp算法,并更改成更方便使用的算法代码模版
//-----生成一个其值等于chars的串T-----
Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
int i;
if (strlen(chars) > MAXSTRLEN)
return ERROR;
else {
T[0] = strlen(chars);
for (i = 1; i <= T[0]; i++)
T[i] = *(chars + i - 1);
return OK;
}
}
//-----KMP算法-----
int Index_KMP(SString S,SString T,int pos){//利用next函数求模式串T在主串S第pos个字符之后的位置
i=pos;j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}
//-----计算next函数值-----
void get_next(SString T,int next[]){
i=1;next[1]=0;j=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
}
T与chars相比T[0]存储的是字符串长度。这里将其改成适合acm的KMP算法模板代码
#include<cstdio> #include<cstring> int next[1010]; int count; char s[1010],p[1010]; void get_next(char* p){ int i=0,j,len=strlen(p); next[0]=j=-1; while(i<len-1){ if(j==-1||p[i]==p[j]){ ++i,++j; next[i]=j; } else j=next[j]; } } int kmp(char* s,char* p){ int i=0,j=0,len1=strlen(s),len2=strlen(p); while(i<len1){ if(s[i]==p[j]||j==-1){ i++,j++; } else{ j=next[j];//加速过程 } //if(j==len2) //count++; if(j==len2)//返回str第一次出现的下标 return i-len2; } //return count;//返回模式串出现的次数k } int main(){ while(scanf("%s %s",s,p)!=EOF){ get_next(p); printf("%d\n",kmp(s,p)); } return 0; }