串匹配问题的BF算法和KMP算法

2019-11-06 06:55:48

字体：大中小

来源：转载

供稿：网友

习题：假设在文本“ababcabccabcacbab”中查找模式“abcac”，写出分别采用BF算法和KMP算法的串匹配过程。 1.BF算法：简单的模式匹配输入：主串S,模式T 输出：T在S中的位置 1.初始化主串比较的开始位置index=0; 2.在串S和串T中设置比较的起始下标i=0,j=0; 3.重复下述操作，直到S或T的所有字符均比较完毕： 3.1 如果S[i]=T[j]，则继续比较S和T的下一对字符； 3.2 否则，下一趟匹配的开始位置index++，回溯下标i=index,j=0; 4.如果T中所有字符均比较完，则返回匹配的开始长度index；否则返回0；

#include <iostream>using namespace std;int BF(char S[],char T[]){ int index=0; int i(0),j(0); while((S[i]!='/0'&&T[j]!='/0')) { if(S[i]==T[j]) {i++;j++;} else { index++; i=index;j=0; } } if(T[j]=='/0') return index+1; else return 0;}int main(){ char S[]={"ababcabccabcacbab"},T[]={"abcac"}; cout<<BF(S,T)<<endl; return 0;}

2.KMP算法主要是针对一次匹配失败后，主串和模式的下标回溯的优化。

输入：主串S,模式T 输出：T在S中的位置 1.在串S和串T中分别设置比较的起始下标i=0,j=0; 2.重复下述操作，直到S或T的所有字符均比较完毕： 2.1 如果S[i]=T[j]，则继续比较S和T的下一对字符串 2.2 否则将下标回溯到next[j],即j=next[j]; 2.3 如果j=-1,则将下标i和j分别加1，准备下一次比较； 3.如果T中所有字符均比较完毕，则返回本趟匹配的开始位置，否则返回0；

#include <iostream>#include <string>using namespace std;void GetNext(char T[],int next[]){ int i,j,len; next[0]=-1; for(j=1;T[j]!='/0';j++) { for(len=j-1;len>=1;len--) { for(i=0;i<len;i++) if(T[i]!=T[j-len+i]) break; if(i==len) { next[j]=len;break; } } if(len<1) next[j]=0; }}int KMP(char S[],char T[]){ int i=0,j=0; int next[80]; GetNext(T,next); while(S[i]!='/0'&&T[j]!='/0') { if(S[i]==T[j]) { i++;j++; } else { j=next[j]; if(j==-1) { i++;j++; }} } if(T[j]=='/0') return(i-strlen(T)+1); else return 0;}int main(){ char S[]={"ababcabccabcacbab"},T[]={"abcac"}; cout<<KMP(S,T)<<endl; return 0;}

能够理解，也能够花时间磨出代码，等待继续熟悉。还有next值的优化算法

上一篇：Opengl之图元重启动

下一篇：我的学习笔记之兔子的只数