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

字符串模式匹配---BF算法
字符串模式匹配有着广泛的应用，如求最大公共子串、最长回文字符串、L-Gap、数据压缩、DNA序列匹配等问题。所谓模式匹配就是在目标字符串中寻找字串的过程，要寻找的字串即为模式。
BF(BruceForce)算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的字串，则匹配失败。
该算法较为简单，代码如下：//start为从第start位置的字符开始比较，默认为0
intBF(chars[],chard[],intstart=0)
{
char*p=s+start;//记录开始比较的位置intindex=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')//匹配成功，返回结果returnindex;
else//主串和模式串回溯{
++p;
q=d;
}
}
return-1;//匹配失败}

设有主串s和子串t，子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t。
传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。
KMP算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。下面说说KMP算法的原理。

KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一．简单匹配算法
先来看一个简单匹配算法的函数：
intIndex_BF(charS[],charT[],intpos)
{
/*若串S中从第pos(S的下标0≤pos<StrLength(S))个字符
起存在和串T相同的子串，则称匹配成功，返回第一个
这样的子串在串S中的下标，否则返回-1*/
inti=pos,j=0;
while(S[i+j]!='/0'&&T[j]!='/0')
if(S[i+j]==T[j])
j++;//继续比较后一字符
else
{
i++;j=0;//重新开始新的一轮匹配
}
if(T[j]=='/0')
returni;//匹配成功返回下标
else
return-1;//串S中(第pos个字符起)不存在和串T相同的子串
}//Index_BF
此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从j=0起比较S[i+j]与T[j]，若相等，则在主串S中存在以i为起始位置匹配成功的可能性，继续往后比较(j逐步增1)，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i增1，而j退回至0，重新开始新一轮的匹配。
例如：在串S=”abcabcabdabba”中查找T=”abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1]和T[1]是否相等…我们发现一直比较到S[5]和T[5]才不等。如图：

当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：

这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：

这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：

又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图：
二.KMP匹配算法
还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5]和T[5]不等后，S下标