字符串模式匹配---BF算法VIP免费

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