1、字符串模式匹配 -BF算法 字符串模式匹配有着广泛的应用，如求最大公共子串、最长回文字符串、 L-Gap、数据压缩、 DNA序列匹配等问题。所谓模式匹配就是在目标字符串中寻找字串的过程，要寻找的字串即为模式。 BF(Bruce Force)算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的 start 位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1 位置，继续进行比较直至模式串的所有字符都已比较成功则匹配成功，或者 主串所有的字符已经比较完毕，没有找到完全匹配的字串，则匹配失败。 该算法较为简
2、单，代码如下： /start 为从第 start 位置的字符开始比较，默认为 0 int 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 +q; if (*q = 0) /匹配成功，返回结果 return index; else /主串和模式串回溯 +p; q = d; retur
3、n -1; /匹配失败 设有主串 s 和子串 t，子串 t 定位是指在主串 s 中找到一个与子串 t 相等的子串。通常把主串 s 称为目标串，把子串 t 称为模式串，因此定位也称作模式匹配。 模式匹配成功是指在目标串 s 中找到一个模式串 t。 传统的 字符串模式匹配算法（也就是 BF 算法） 就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为 O（ n m），其中 n 和 m 分别为串 s 和串 t 的长度。 KMP 算法是由 Knuth， Morris 和 Pratt 等人共同提出的 ，所以成为 KnuthMorris P
4、ratt 算法，简称 KMP 算法。 KMP 算法是字符串模式匹配中的经典算法。和 BF算法相比， KMP 算法的不同点是匹配过程中， 主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为 O（ n m）。下面说说 KMP 算法的原理。 KMP 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为 O(m*n);KMP 匹配算法。可以证明它的时间复杂度为 O(m+n).。 一 简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S , char T , int pos ) /* 若串 S 中从第 pos(S 的下标
5、 0pos S0 != 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和
6、 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
7、中下标为 j 的字符，如果与首字符 相同，且 j 的前面的 1 k 个字符与开头的 1 k 个字符不等（或者相等但 Tk=Tj）（ 1k0 但 kn, 表示 ,Sm的前 k个字符与 T中的开始 k个字符已经间接比较相等了，下一次比较 Sm和 Tk相等吗？ 4. 其他值，不可能。 四 . 求串 T 的模式值 nextn的函数 说了 这么多，是不是觉得求串 T 的模式值 nextn很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明 KMP 算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数 : void get_next
8、val(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; else nextj = nextk; / if else k = nextk; / while /这里是我加的显示部分 / for(int i=0;ij;i+) / / coutnexti; / /coutendl; / get_nextval 另一种写法，也差不多。 void getNext(const char* pattern,int next)
