浅谈字符串匹配算法—BF 算法及 KMP 算法.doc

《浅谈字符串匹配算法—BF 算法及 KMP 算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、字符串匹配，在实际编程中经常遇到。其相应的算法有很多，本文就BF算法和KMP算法，谈一下自己的理解。并结合平时编程，修改了一下，使其更符合我们的使用习惯。(注：标准BF算法和KMP算法，为研究方便，其字符数组[0]存放的都是字符吊的长度。本文讲解中，并没有保存字符串长度。后面给出的示例代码中，字符数组中是否保存有字符串长度，都给出了相应的算法代码。)一、BF算法(BruteForce):BF算法核心思想是：首先S⑴和T⑴比较，若相等，则再比较S[2]和T[2],—直到T[M]为止；若S⑴和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如

2、果存在k,1

3、符的位置，即S回溯到S[1]的位置，T冋溯到T[0]的位置,再重新开始比较。此时,S⑴和T[0]、S⑵和T⑴……如果再次发现不兀配字符，则再次回溯，即S回溯到S[2]的位置，T回到T[0]的位置。循环往复，直到到达S或者T字符申的结尾。如果是到达S审的结尾，则表示匹配失败，如果是到达T串的结尾，则表示匹配成功。BF算法优点：思想简单，直接，无需对字符串S和T进行预处理。缺点:每次字符不匹配时，都要回溯到开始位置，时间开销大。下面是BF算法的代码实现：bf.c#include#include#include

4、ring.h>intindcx_bf(char*s,char*t,intpos):intindex_bLself(char*s,char*l,iniindex);/*BF算法示例7inimain(){chars[]=”6he3wor”;〃标准BF算法中,s[0]和t[0]存放的为字符串长度。chart[]="3wor";intm=index_bf(s,t,2);〃标准BF算法printf(,'index_bf:%d',,m);m=index_bf_self(s,t,2);〃修改版BF算法，s和t中，不必再存放字符串反度。printf(,'ind

5、ex_bf_self:%d',,m);exit(O);}字符串S和T屮,S0MO]存放必须为字符串长度例:s[]="7hibaby!11T[]="4baby"index_bf(s,t,1);pos：在S中要从下标pos处开始資找T(说明:标准BF算法屮,为研究方便,s[Oht[O】屮存放的为各门字符串长度。)*/intindex_bf(char*s,char*t,intpos){inti,j；if(pos>=l&&pos<=s[O]-'O'){i=pos;j=l；whilc(i<=s[0]-,0'&&j<=t[0]-'0,){if(s[i]==

6、tU])i++；j++;}else{j=I;i=i-j+2;){returni-tfO]+'O';})return-1;}else{return-1;修改版,字符串S和t屮，不必再包含字符串长度。例:s[]=Mhibaby"t[]=,,baby>,index_bf_self(s,t,O);index:在s屮,从儿号下标开始查找*/intindex_bfLself(char*s,char*t,intindex)(inti=index,j=O;while(s[i]!=,O,){while(*(t+j)!='O*&&*(s+i+j)!=,O,){i

7、f(*(t+j)!=*(s+i+j))break;j++；returni;}i++；j=0;)return-1;}测试结果：二、KMP算法：由BF算法例图中可知，当S⑹和T⑹不匹配时，S和T都需要冋溯，吋间复朵度高。因此，出现了KMP算法。先看下图：从图中，我们可以很容易的发现，S不必回溯到S[1]的位置，T也不必回溯到T[0]的位置，因为前面的字符,S和T中都是相等的。如果S不回溯的话，那T该怎么办呢？我们也可以很容易的发现，S中5、6、7号字符和T中0、1、2号字符是相等的。故T育•接回溯到T[3]的位置即可。此时我们就省去了很多不必要的回溯和

8、比较。那么这些都是我们从图中直观得出的结论，如果换做其他字符,我们乂如何知道T该回溯到几号字符呢？先看看KMP算法的思想：