字符串匹配算法总结.docx

Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。_ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible ( 业内人士一般简称TAOCP). 稍稍提一下，有个叫H.A.Simon 的家伙，不仅拿了Turing Award ，顺手拿了个Nobel Economics Award ，做了AI 的爸爸，还是Chicago Univ 的Politics PhD ，可谓全才。 KMP 的思想是这样的： 利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离 比如 模式串ababac 这个时候我们发现在c 处不匹配，然后我们看c 前面那串字符串的最大相等前后缀，然后再来移动 下面的两个都是模式串，没有写出来匹配串 原始位置 ababa c 移动之后 aba bac 因为后缀是已经匹配了的，而前缀和后缀是相等的，所以直接把前缀移动到原来后缀处，再从原来的c 处，也就是现在的第二个b 处进行比较。 这就是KMP 。 Horspool 算法。 当然，有市场就有竞争，字符串匹配这么大一个市场，不可能让BF 和KMP 全部占了，于是又出现了几个强劲的对手。 第一个登场的是 Horspool 算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大，为后来的算法影响很大。 匹配串：abcbc sdxzcxx 模式串：cbcac 这个时候我们从右向左进行对暗号，c-c ，恩对上了，第二个b-a ，不对啊，我们应该怎么办？难道就这么放弃么。于是，模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符b 的位置，结果发现居然有，赶快对上赶快对上，别耽误了。 匹配串：abcbcsd xzcxx 模式串： cbcac 然后继续从最右边的字符从右向左进行比较。这时候，我们发现了，d-c 不匹配啊，而且模式穿里面没有噢，没办法，只好移动一个模式串长度的单位了。 匹配串：abcbcsdxzcxx 模式串： cbcac Boyer-Moore算法 是一个很复杂的算法，当然，虽然理论上时间复杂度和KMP 差不多，但是实际上却比KMP 快数倍，可见实践是检验真理的唯一标准。 分为两步预处理，第一个是bad-character heuristics ，也就是当出现错误匹配的时候，移位，基本上就是做的Horspool 那一套。 第二个就是good-suffix heuristics ，当出现错误匹配的时候，我还要从不匹配点向左看啊，以前匹配的那段子字符串是不是在模式串本身中还有重复的啊，有重复的话，那么我就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较 匹配串：abaccba bbazz 模式串：cbadcba 我们看到已经匹配好了cba ，但是c-d 不匹配，这个时候我们发现既可以采用bad-character heuristics ，也可以使用good-suffix heuristics( 模式串：cba dcba ) ，在这种情况下，邪不压正。毅然投奔good 。移动得到 匹配串：abaccbabbaz z 模式串： cbadcba 可是，我们有时候也发现，已经匹配好的那一部分其实并没有再有重复了的啊。这个时候，我们发现已经匹配好的那串字符串有一部分在开头重新出现了，那么，赶快，对齐吧。 匹配串：abacccb bbazz 模式串：cbadccb 然后得到 匹配串：abacccbbbazz 模式串： cbadccb 当两种Good-Suffix 出现的时候，取移动距离最大的那个。Sunday算法 最后一个是Sunday 算法，实际上比Boyer-Moore 还快，呵呵。长江后浪推前浪。 看原始论文的题目，D.M. Sunday 貌似是故意想气气Boyer-Moore 两位大牛似的。呵呵。不过实际上的确Sunday 算法的确比BM 算法要快，而且更简单。Sunday 的算法思想和Horspool 有些相似，但是。当出现不匹配的时候，却不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右边对齐的右一位的那个字符在模式串的位置。 比如： 匹配串：abcbc zdxzc 模式串：zbcac 恩，这里我们看到b-a 没有对上，我们就看匹配串中的z 在模式串的位置，然后，嘿嘿。 匹配串：abcbczdxzc 模式串： zbcac 如果模式串中的没有那个字符怎么办呢？很简单，跳过去呗。 匹配串：abcbc edxzcs 模式串：zbcac e 不在模式串中出现 那么我们就 匹配串：abcbcedxzcs 模式串： zbcac (2009/10/20补充) RK算法 某一天在图书馆的一本算法分析设计书上翻到的。思路很新颖！和大家分享下。 在串匹配的简单算法中，把文本每m个字符构成的字符段作为一个字段，和模式进行匹配检查。如果能对一个长度为m的字符 串赋以一个Hash函数。那么显然只有那些与模式具有相同hash函数值的文本中的字符串才有可能与模式匹配，这是必要条件 ，而没有必要去考虑文本中所有长度为m的字段，因而大大提高了串匹配的速度。因此RK算法的思想和KMP，BM，Sunday等思 路迥然不同！ （事实上，之前的串匹配方法，是将模式串的一个一个字符作为小的特征去分别进行匹配，而RK算法则是将串整体作为一个 特征！难就难在单个字符的特征很容易想得到，整体作为一个特征就没那么容易想得到了） 如果把整体作为一个特征，那么如何快速的求出这个整体特征的特征值？ 模式串的特征值仅需求一次即可。对于文本中的任意m个字符构成的字串如何快速的求特征就是个难点了。 抛砖引玉，这里给出一个简单的特征计算。 将字符串的每一个字符看做一个数，那么这个字符串的就是一个数字数组，通 过积分向量可以快速任意一个长度子字符串的向量和。可以把字符串的对应的字符数组的元素和看做这个字符串整体特征。 这个特征是可以再O（1）的时间内求出的。其实原始的RK算法里面是把字符串看做一个26进制数在计算特征的。这里就不啰 嗦了，有兴趣的可以深入查找 aabsee sds 模式串 ees ees 发现 see向量和 = ees的向量和 然后就对see和ees做逐个字符的比较。发现不匹配继续往下走 aabsees ds 模式串 ees ees 发现 ees向量和 = ees的向量和 然后就对ees和ees做逐个字符的比较。发现匹配OK。 另外还有 字符串匹配自动机 后缀树算法（分在线和非在线两种）等 见如下文章。不能说那个比那个更好，各个算法都有自己的优势及最佳应用场合。参考： /yifan403/archive/2009/06/16/4272793.aspx 另外，关于多模式字符串匹配 有AC算法（字符串匹配自动机思想） WM算法（BM在多模式的推广应用） 参考： /ijuliet/category/498465.aspx 该女子的blog有很多好文章。 /*华丽分割线*/ 附上sunday代码： /kmj0217/blog/item/6f837f2f3da097311e3089cb.html 一种比KMP 和 BM 更高效的匹配算法（如果想看原英文介绍，看下面分割线后的网址） 适用于：模式串较短的情况，最坏时间复杂性为O(N*M)，不过一般没这么坏 Sunday 算法其实思想跟BM算法很相似，只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有 在匹配串中出现则直接跳过，即移动步长= 匹配串长度+ 1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。 代码如下： /* Sunday-字符串匹配算法 - 一种优于 KMP 的算法 思想类似于BM 算法，只不过是从左向右匹配 遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置 另外：采用BM/KMP 的预处理的做法，事先计算好移动步长 ，等到遇到不匹配的值直接使用 */ #include #include using namespace std; /一个字符8位 最大256种 #define MAX_CHAR_SIZE 256 /*设定每个字符最右移动步长，保存每个字符的移动步长 如果大串中匹配字符的右侧一个字符没在子串中，大串移动步长= 整个串的距离 +1 如果大串中匹配范围内的右侧一个字符在子串中，大串移动距离= 子串长度 - 这个字符在子串中的位置 */ int *setCharStep(char *subStr) int *charStep=new intMAX_CHAR_SIZE; int subStrLen=strlen(subStr); for(int i=0;iMAX_CHAR_SIZE;i+) charStepi=subStrLen+1; /从左向右扫描一遍 保存子串中每个字符所需移动步长 for(int i=0;isubStrLen;i+) charStep(unsigned char)subStri =subStrLen-i; return charStep; /* 算法核心思想，从左向右匹配，遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置 根据事先计算好的移动步长移动大串指针，直到匹配 */ int sundaySearch(char *mainStr,char *subStr,int *charStep) int mainStrLen=strlen(mainStr); int subStrLen=strlen(subStr); int main_i=0; int sub_j=0; while(main_imainStrLen) /保存大串每次开始匹配的起始位置，便于移动指针 int tem=main_i; while(sub_j mainStrLen) return -1; /否则 移动步长 重新匹配 char firstRightChar=mainStrtem+subStrLen; main_i =tem + charStep(unsigned char)firstRightChar; sub_j=0; break;/退出本次失败匹配 重新一轮匹配 if(sub_j = subStrLen) return main_i-subStrLen; return -1; int main() char *mainStr=absaddsasfasdfasdf; char *subStr=dd; int *charStep=setCharStep(subStr); cout位置： sundaySearch(mainStr,subStr,charStep)endl; system(pause); return 0; /*华丽的分割线*/ 算法介绍以及实现伪码：http:/www-igm.univ-mlv.fr/lecroq/string/node19.html void preQsBc(char *x, int m, int qsBc) int i; for (i = 0; i ASIZE; +i) qsBci = m + 1; for (i = 0; i m; +i) qsBcxi = m - i; void QS(char *x, int m, char *y, int n) int j, qsBcASIZE; /* Preprocessing */ preQsBc(x, m, qsBc); /* Searching */ j = 0; while (j = n - m) if (memcmp(x, y + j, m) = 0) OUTPUT(j); j += qsBcyj + m; /* shift */ / 第三个代码实现，貌似比较高效 /azuryy/blog/item/10d3d3460b97af0e6b63e5cd.html 头文件定义： /* Sunday.h */ class Sunday public: Sunday(); Sunday(); public: int find(const char* pattern, const char* text); private: void preCompute(const char* pattern); private: /Lets assume all characters are all ASCII static const int ASSIZE = 128; int _tdASSIZE ; int _patLength; int _textLength; ; 源文件 /* Sunday.cpp */ Sunday:Sunday() Sunday:Sunday() void Sunday:preCompute(const char* pattern) for(int i = 0; i ASSIZE; i+ ) _tdi = _patLength + 1; const char* p; for ( p = pattern; *p; p+) _td*p = _patLength - (p - pattern); int Sunday:find(const char* pattern, const char* text) _patLength = strlen( pattern ); _textLength = strlen( text ); if ( _patLength = 0 | _textLength = 0) return -1; preCompute( pattern ); const char *t, *p, *tx = text; while (tx + _patLength = text + _textLength) for (p = pattern, t = tx; *p; +p, +t) if (*p != *t) break; if (*p = 0) return tx-text; tx += _tdtx_patLength; return -1; 简单测试下： int main() char* text = blog.csdn,; char* pattern = csdn,blog ; Sunday sunday; printf(The First Occurence at: %d/n,sunday.find(pattern,text); return 1; / strstr的实现。 需要说明的是strstr是c语言提供的使用Brute Force实现的字符串匹配，简单、通用是其最大的优点。时间复杂度是O(mn) / 下面是Microsoft的实现 /经典算法 /比KMP算法简单,没有KMP算法高效 char * _cdecl strstr ( const char * str1, const char * str2 ) char *cp = (char *) str1; char *s1, *s2; if ( !*str2 ) return(char *)str1); while (*cp) s1 = cp; s2 = (char *) str2; while ( *s1 & *s2 & !(*s1-*s2) ) s1+, s2+; if (!*s2) return(cp); cp+; return(NULL); strstr glibc里的strstr函数用的是brute-force(naive)算法，它与其它算法的区别是strstr不对