文档介绍：..页眉.. 页脚. 字符串模式匹配---BF 算法字符串模式匹配有着广泛的应用,如求最大公共子串、最长回文字符串、L-Gap 、数据压缩、DNA 序列匹配等问题。所谓模式匹配就是在目标字符串中寻找字串的过程,要寻找的字串即为模式。 BF(Bruce Force) 算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的 start 位置开始与模式串进行匹配,如果相等, 则继续比较后续字符,如果不相等则模式串回溯到开始位置,主串回溯到 start+1 位置,继续进行比较直至模式串的所有字符都已比较成功则匹配成功, 或者主串所有的字符已经比较完毕,没有找到完全匹配的字串,则匹配失败。该算法较为简单,代码如下: //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' &&*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 (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). 。一. 简单匹配算法先来看一个简单匹配算法的函数: ..页眉.. 页脚. int Index_BF ( char S[ ], char T[ ], int pos ) { /* 若串 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') return i; // 匹配成功返回下标 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 下标回溯