字符串模式匹配---BF算法.doc

字符串模式匹配-BF算法字符串模式匹配有着广泛的应用，如求最大公共子串、最长回文字符串、L-Gap、数据压缩、DNA序列匹配等问题。所谓模式匹配就是在目标字符串中寻找字串的过程，要寻找的字串即为模式。BF(Bruce Force)算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的字串，则匹配失败。该算法较为简单，代码如下：/start 为从第start位置的字符开始比较，默认为0int BF(char s, char d, int start = 0) char *p = s + start; /记录开始比较的位置 int index = start - 1; /记录位置，以便成功时返回字串在主串的位置 char *q = d; char *tmp; while (*p != 0) tmp = p; +index; while (*q != 0 & *tmp != 0 & *tmp = *q) +tmp; +q; if (*q = 0) /匹配成功，返回结果 return index; else /主串和模式串回溯 +p; q = d; return -1; /匹配失败 设有主串s和子串t，子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t。 传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（nm），其中n和m分别为串s和串t的长度。 KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为KnuthMorrisPratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（nm）。下面说说KMP算法的原理。KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。一简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos )/*若串S中从第pos(S的下标0posS0!= S1,S1 != S2,所以S1!= T0,S2 != T0.还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn呢？（本文中next值、模式函数值、模式值是一个意思。）三.怎么求串的模式值nextn定义：（1）next0= -1意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad”则next6=-1，因T3=T6（3）nextj=k意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj != Tk（1kj）。即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1且Tj != Tk.（1kj）;(4) nextj=0意义：除（1）（2）（3）的其他情况。举例：01）求T=“abcac”的模式函数的值。next0= -1根据（1）next1=0根据(4)因（3）有1=kj;不能说，j=1,Tj-1=T0next2=0根据(4)因（3）有1=k0但kn,表示,Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？4.其他值，不可能。四.求串T的模式值nextn的函数说了这么多，是不是觉得求串T的模式值nextn很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数:void get_nextval(const char *T, int next)/求模式串T的next函数值并存入数组next。int j = 0, k = -1;next0 = -1;while ( Tj/*+1*/ != /0 )if (k = -1 | Tj = Tk)+j; +k;if (Tj!=Tk)nextj = k;elsenextj = nextk;/ ifelsek = nextk;/ while/这里是我加的显示部分/ for(inti=0;ij;i+)/coutnexti;/coutendl;/ get_nextval另一种写法，也差不多。void getNext(const char* pattern,int next)next0=-1;int k=-1,j=0;while(patternj!=/0)if(k!=-1&patternk!=patternj )k=nextk;+j;+k;if(patternk=patternj)nextj=nextk;elsenextj=k;/这里是我加的显示部分/ for(inti=0;ij;i+)/coutnexti;/coutendl;下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数#include #include int KMP(const char *Text,const char* Pattern) /const表示函数内部不会改变这个参数的值。if( !Text|!Pattern|Pattern0=/0|Text0=/0 )/return -1;/空指针或空串，返回-1。int len=0;const char * c=Pattern;while(*c+!=/0)/移动指针比移动下标快。+len;/字符串长度。int *next=new intlen+1;get_nextval(Pattern,next);/求Pattern的next函数值int index=0,i=0,j=0;while(Texti!=/0& Patternj!=/0 )if(Texti= Patternj)+i;/继续比较后继字符+j;elseindex += j-nextj;if(nextj!=-1)j=nextj;/模式串向右移动elsej=0;+i;/whiledelete next;if(Patternj=/0)return index;/匹配成功elsereturn -1;int main()/abCabCadchar* text=bababCabCadcaabcaababcbaaaabaaacababcaabc;char*pattern=adCadCad;/getNext(pattern,n);/get_nextval(pattern,n);coutKMP(text,pattern)endl;return 0;五其他表示模式值的方法上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next0= -1,但后面绝不会出现-1，除了next0，其他模式值nextj=k(0kj)的意义可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求Tj != Tk。其实next0也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next0=0的），这样，nextj=k(0kj)的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。下面给出几种方法的例子：表一。下标012345678Tababcaabc(1) next-10-102-1102(2) next-100120112(3) next010130213第三种表示方法,在我看来，意义不是那么明了，不再讨论。表二。下标01234Tabcac(1)next-100-11(2)next-10001表三。下标01234567TadCadCad(1)next-100-100-10(2)next-10001234对比串的模式值第一种表示方法和第二种表示方法，看表一：第一种表示方法next2= -1,表示T2=T0，且T2-1 !=T0第二种表示方法next2= 0,表示T2-1 !=T0,但并不管T0和T2相不相等。第一种表示方法next3= 0,表示虽然T2=T0，但T1 =T3第二种表示方法next3= 1,表示T2 =T0,他并不管T1和T3相不相等。第一种表示方法next5= -1,表示T5=T0，且T4 !=T0，T3T4 !=T0T1，T2T3T4 !=T0T1T2第二种表示方法next5= 0,表示T4 !=T0，T3T4 !=T0T1，T2T3T4 !=T0T1T2，但并不管T0和T5相不相等。换句话说：就算T5=x,或T5=y,T5=9,也有next5= 0。从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=“adCadCBdadCadCad 9876543”中匹配串T=“adCadCad”,用第一种表示方法写出的模式匹配函数,当比较到S6 != T6时，取next6= -1（表三）,它可以表示这样许多信息：S3S4S5=T3T4T5=T0T1T2，而S6 != T6，T6=T3=T0，所以S6 != T0,接下来比较S7和T0吧。如果用第二种表示方法写出的模式匹配函数,当比较到S6 != T6时，取next6= 3（表三）,它只能表示：S3S4S5= T3T4T5=T0T1T2，但不能确定T6与T3相不相等，所以，接下来比较S6和T3;又不相等，取next3= 0，它表示S3S4S5= T0T1T2，但不会确定T3与T0相不相等，即S6和T0相不相等，所以接下来比较S6和T0，确定它们不相等，然后才会比较S7和T0。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：她说：“next函数值的含义是：当出现Si !=Tj时，下一次的比较应该在Si和Tnextj之间进行。”虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法next值，就是前面的get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第一次学到这里，不参考其他资料和明白人讲解的情况下，就能搞懂这个算法（我的意思是不仅是算法的大致思想，而是为什么定义和例子中nextj=k(0kj)，而算法中nextj=k(-1kj)）。凭良心说：光看这个讲座，我就对这个教受十分敬佩，不仅讲课讲得好，声音悦耳，而且这门课讲得层次分明，恰到好处。在KMP这个问题上出了点小差错，可能是编书的时候，在这本书上抄下了例子，在那本书上抄下了算法，结果不怎么对得上号。因为我没找到原书，而据有的网友说，书上已不是这样，也许吧。说起来，教授们研究的问题比这个高深不知多少倍，哪有时间推演这个小算法呢。总之，瑕不掩玉。书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从S的任何位置开始匹配T，“当出现Si !=Tj时，下一次的比较应该在Si和Tnextj之间进行。”定义next0=0。void myget_nextval(const char *T, int next)/求模式串T的next函数值（第二种表示方法）并存入数组next。int j = 1, k = 0;next0 = 0;while ( Tj != /0 )if(Tj = Tk)nextj = k;+j; +k;else if(Tj != T0)nextj = k;+j;k=0;elsenextj = k;+j;k=1;/whilefor(inti=0;ij;i+)coutnexti;coutendl;/ myget_nextval下面是模式值使用第二种表示方法的匹配函数（next0=0）int my_KMP(char *S, char *T, int pos)int i = pos,j = 0;/pos(S的下标0posStrLength(S)while ( Si != /0 & Tj != /0 )if (Si = Tj )+i;+j; /继续比较后继字符else/ ababcaabc/ 000120112/-10-102 -1102i+;j = nextj;/*当出现Si !=Tj时，下一次的比较应该在Si和Tnextj之间进行。要求next0=0。在这两个简单示范函数间使用全局数组next传值。*/whileif ( Tj = /0 )return (i-j); /匹配成功elsereturn -1; / my_KMP六后话-KMP的历史这段话是抄的Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knuth和Pratt努力地重建了Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是“灵光一现”中被发现的，而理论化的计算机科学确实在一些时候会应用到实际的应用中。