C语言：串的模式匹配算法
BF算法(穷举)：
inti=pos;//i用于主串parent中的起始位置
intj=1;//子串的起始位置
while(i<=parent->length&&j<=child->length){
if(parent->ch[i-1]==child->ch[j-1]){
i++;
j++;
}else{
i=i-j+2;//i回朔到上次匹配的首位的下一位
j=1;//j回到子串的第一个位置
}
}
if(j>child->length){
returni-child->length;
}
return0;
}
KMP算法（不回溯指针i，利用部分匹配值将指针向右滑到尽可能远的距离，速度快）：
部分匹配值的计算：
inti=0;
intj=-1;
next[0]=-1;
while(i<child.length){
if(j==-1||child.ch[i]==child.ch[j]){
++i;
++j;
next[i]=j;
}else{
j=next[j];
}
}
KMP算法实现时与BF算法区别
else{
j=next[j];//
}
}
if(j==child->length){
return(i+1)-j;
}
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。
