数据结构- 串的模式匹配算法：bf和 kmp算法

《数据结构- 串的模式匹配算法：bf和 kmp算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本文由西安白癜风专科医院http://www.xapfb120.com/收集，转载请注明出处数据结构-串的模式匹配算法：BF和KMP算法Brute-Force算法的思想1．BF(Brute-Force)算法Brute-Force算法的基本思想是：1)从目标串s的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s的第二个字符起再重新和串t进行比较。2)依此类推，直至串t中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s中的位置就是t在s中的位置，

2、否则模式匹配不成功。Brute-Force算法的实现本文由西安白癜风专科医院http://www.xapfb120.com/收集，转载请注明出处本文由西安白癜风专科医院http://www.xapfb120.com/收集，转载请注明出处c语言实现：1.//Test.cpp:Definestheentrypointfortheconsoleapplication.2.//3.#include"stdafx.h"4.#include5.#include"stdlib.h"6.#include

3、m>7.usingnamespacestd;8.9.//宏定义10.#defineTRUE111.#defineFALSE012.#defineOK113.#defineERROR014.15.#defineMAXSTRLEN10016.17.typedefcharSString[MAXSTRLEN+1];18./************************************************************************/19./*20.返回子串T在主串S中第pos位置之后的位置，若不

4、存在，返回021.*/22./************************************************************************/23.intBFindex(SStringS,SStringT,intpos)24.{25.if(pos<1

5、

6、pos>S[0])exit(ERROR);26.inti=pos,j=1;27.while(i<=S[0]&&j<=T[0])28.{29.if(S[i]==T[j])30.{31.++i;++j;32.}else{33.i=i-j+2;

7、34.j=1;35.}36.}37.if(j>T[0])returni-T[0];38.returnERROR;39.}40.41.42.本文由西安白癜风专科医院http://www.xapfb120.com/收集，转载请注明出处本文由西安白癜风专科医院http://www.xapfb120.com/收集，转载请注明出处43.voidmain(){44.SStringS={13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};45.SStringT={5,'a',

8、'b','c','a','c'};46.intpos;47.pos=BFindex(S,T,1);48.cout<<"Pos:"<

9、ww.xapfb120.com/收集，转载请注明出处需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是高效率的?现在讨论一般情况:假设主串：s:„s(1)s(2)s(3)……s(n)‟;模式串：p:„p(1)p(2)p(3)…..p(m)‟现在我们假设主串第i个字符与模式串的第j(j<=m)个字符„失配‟后，主串第i个字符与模式串的第k(k

10、..P(j-1)’=’S(i-j+1)……S(i-1)’从而推导出k到j-1位的“部分匹配”：即P的j-1～j-k＝S前i-1～i-(k-1))位‘P(j-k+1)…..P(j-1)’=’S(i-k+1)S(i-k+2)……S(i-1)’由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-