字符串匹配算法總結

1、Brute Force(BF或蠻力搜索) 算法： 這是世界上最簡單的算法了。 首先將匹配串和模式串左對齊，然后從左向右一個一個進行比較，如果不成功則模式串向右移動一個單位。 速度最慢。 那么，怎么改進呢？ 我們注意到Brute Force 算法是每次移動一個單位，一個一個單位移動顯然太慢，是不是可以找到一些辦法，讓每次能夠讓模式串多移動一些位置呢？ 當然是可以的。 我們也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的時候，前面匹配成功的信息都被當作廢物丟棄了，當然，就如現(xiàn)在的變廢為寶一樣，我們也同樣可以將前面匹配成功的信息利用起來，極大地減少計算機的處理時間

2、，節(jié)省成本。_ 注意，蠻力搜索算法雖然速度慢，但其很通用，文章最后會有一些更多的關于蠻力搜索的信息。 KMP算法 首先介紹的就是KMP 算法。 這個算法實在是太有名了，大學上的算法課程除了最笨的Brute Force 算法，然后就介紹了KMP 算法。也難怪，呵呵。誰讓Knuth D.E. 這么world famous 呢，不僅拿了圖靈獎，而且還寫出了計算機界的Bible <The Art of Computer Programming>( 業(yè)內人士一般簡稱TAOCP). 稍稍提一下，有個叫H.A.Simon 的家伙，不僅拿了Turing Award ，順手拿了個Nobel Econ

3、omics Award ，做了AI 的爸爸，還是Chicago Univ 的Politics PhD ，可謂全才。 KMP 的思想是這樣的： 利用不匹配字符的前面那一段字符的最長前后綴來盡可能地跳過最大的距離 比如 模式串ababac 這個時候我們發(fā)現(xiàn)在c 處不匹配，然后我們看c 前面那串字符串的最大相等前后綴，然后再來移動 下面的兩個都是模式串，沒有寫出來匹配串 原始位置 ababa c 移動之后 aba bac 因為后綴是已經匹配了的，而前綴和后綴是相等的，所以直接把前綴移動到原來后綴處，再從原來的c 處，也就是現(xiàn)在的第二個b 處進行比較。 這就是KMP 。 Horspool 算法。 當然

4、，有市場就有競爭，字符串匹配這么大一個市場，不可能讓BF 和KMP 全部占了，于是又出現(xiàn)了幾個強勁的對手。 第一個登場的是 Horspool 算法的思想很簡單的。不過有個創(chuàng)新之處就是模式串是從右向左進行比較的。很好很強大，為后來的算法影響很大。 匹配串：abcbc sdxzcxx 模式串：cbcac 這個時候我們從右向左進行對暗號，c-c ，恩對上了，第二個b-a ，不對啊，我們應該怎么辦？難道就這么放棄么。于是，模式串從不匹配的那個字符開始從右向左尋找匹配串中不匹配的字符b 的位置，結果發(fā)現(xiàn)居然有，趕快對上趕快對上，別耽誤了。 匹配串：abcbcsd xzcxx 模式串： cbcac 然后繼

5、續(xù)從最右邊的字符從右向左進行比較。這時候，我們發(fā)現(xiàn)了，d-c 不匹配啊，而且模式穿里面沒有噢，沒辦法，只好移動一個模式串長度的單位了。 匹配串：abcbcsdxzcxx 模式串： cbcac Boyer-Moore算法 是一個很復雜的算法，當然，雖然理論上時間復雜度和KMP 差不多，但是實際上卻比KMP 快數(shù)倍，可見實踐是檢驗真理的唯一標準。 分為兩步預處理，第一個是bad-character heuristics ，也就是當出現(xiàn)錯誤匹配的時候，移位，基本上就是做的Horspool 那一套。 第二個就是good-suffix heuristics ，當出現(xiàn)錯誤匹配的時候，我還要從不匹配點向左看

6、啊，以前匹配的那段子字符串是不是在模式串本身中還有重復的啊，有重復的話，那么我就直接把重復的那段和匹配串中已經匹配的那一段對齊就是了。再比較 匹配串：abaccba bbazz 模式串：cbadcba 我們看到已經匹配好了cba ，但是c-d 不匹配，這個時候我們發(fā)現(xiàn)既可以采用bad-character heuristics ，也可以使用good-suffix heuristics( 模式串：cba dcba ) ，在這種情況下，邪不壓正。毅然投奔good 。移動得到 匹配串：abaccbabbaz z 模式串： cbadcba 可是，我們有時候也發(fā)現(xiàn)，已經匹配好的那一部分其實并沒有再有重復了

7、的啊。這個時候，我們發(fā)現(xiàn)已經匹配好的那串字符串有一部分在開頭重新出現(xiàn)了，那么，趕快，對齊吧。 匹配串：abacccb bbazz 模式串：cbadccb 然后得到 匹配串：abacccbbbazz 模式串： cbadccb 當兩種Good-Suffix 出現(xiàn)的時候，取移動距離最大的那個。Sunday算法 最后一個是Sunday 算法，實際上比Boyer-Moore 還快，呵呵。長江后浪推前浪。 看原始論文的題目，D.M. Sunday 貌似是故意想氣氣Boyer-Moore 兩位大牛似的。呵呵。不過實際上的確Sunday 算法的確比BM 算法要快，而且更簡單。Sunday 的算法思想和Hors

8、pool 有些相似，但是。當出現(xiàn)不匹配的時候，卻不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右邊對齊的右一位的那個字符在模式串的位置。 比如： 匹配串：abcbc zdxzc 模式串：zbcac 恩，這里我們看到b-a 沒有對上，我們就看匹配串中的z 在模式串的位置，然后，嘿嘿。 匹配串：abcbczdxzc 模式串： zbcac 如果模式串中的沒有那個字符怎么辦呢？很簡單，跳過去唄。 匹配串：abcbc edxzcs 模式串：zbcac e 不在模式串中出現(xiàn) 那么我們就 匹配串：abcbcedxzcs 模式串： zbcac (2009/10/20補充) RK算法 某一天在圖書館的

9、一本算法分析設計書上翻到的。思路很新穎！和大家分享下。 在串匹配的簡單算法中，把文本每m個字符構成的字符段作為一個字段，和模式進行匹配檢查。如果能對一個長度為m的字符 串賦以一個Hash函數(shù)。那么顯然只有那些與模式具有相同hash函數(shù)值的文本中的字符串才有可能與模式匹配，這是必要條件 ，而沒有必要去考慮文本中所有長度為m的字段，因而大大提高了串匹配的速度。因此RK算法的思想和KMP，BM，Sunday等思 路迥然不同！ （事實上，之前的串匹配方法，是將模式串的一個一個字符作為小的特征去分別進行匹配，而RK算法則是將串整體作為一個 特征！難就難在單個字符的特征很容易想得到，整體作為一個特征就沒那

10、么容易想得到了） 如果把整體作為一個特征，那么如何快速的求出這個整體特征的特征值？ 模式串的特征值僅需求一次即可。對于文本中的任意m個字符構成的字串如何快速的求特征就是個難點了。 拋磚引玉，這里給出一個簡單的特征計算。 將字符串的每一個字符看做一個數(shù)，那么這個字符串的就是一個數(shù)字數(shù)組，通 過積分向量可以快速任意一個長度子字符串的向量和?？梢园炎址膶淖址麛?shù)組的元素和看做這個字符串整體特征。 這個特征是可以再O（1）的時間內求出的。其實原始的RK算法里面是把字符串看做一個26進制數(shù)在計算特征的。這里就不啰 嗦了，有興趣的可以深入查找 aabsee sds 模式串 ees ees 發(fā)現(xiàn) se

11、e向量和 = ees的向量和 然后就對see和ees做逐個字符的比較。發(fā)現(xiàn)不匹配繼續(xù)往下走 aabsees ds 模式串 ees ees 發(fā)現(xiàn) ees向量和 = ees的向量和 然后就對ees和ees做逐個字符的比較。發(fā)現(xiàn)匹配OK。 另外還有 字符串匹配自動機 后綴樹算法（分在線和非在線兩種）等 見如下文章。不能說那個比那個更好，各個算法都有自己的優(yōu)勢及最佳應用場合。參考： 另外，關于多模式字符串匹配 有AC算法（字符串匹配自動機思想） WM算法（BM在多模式的推廣應用） 參考： 該女子的blog有很多好文章。 /*華麗分割線*/ 附上sunday代碼： 一種比KMP 和 BM 更高效的匹配算

12、法（如果想看原英文介紹，看下面分割線后的網址） 適用于：模式串較短的情況，最壞時間復雜性為O(N*M)，不過一般沒這么壞 Sunday 算法其實思想跟BM算法很相似，只不過Sunday算法是從前往后匹配，在匹配失敗時關注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒有 在匹配串中出現(xiàn)則直接跳過，即移動步長= 匹配串長度+ 1；否則，同BM算法一樣其移動步長=匹配串中最右端的該字符到末尾的距離+1。 代碼如下： /* Sunday-字符串匹配算法 - 一種優(yōu)于 KMP 的算法 思想類似于BM 算法，只不過是從左向右匹配 遇到不匹配的看大串中匹配范圍之外的右側第一個字符在小串中的最右位

13、置 另外：采用BM/KMP 的預處理的做法，事先計算好移動步長 ，等到遇到不匹配的值直接使用 */ #include<iostream> #include<string.h> using namespace std; /一個字符8位 最大256種 #define MAX_CHAR_SIZE 256 /*設定每個字符最右移動步長，保存每個字符的移動步長 如果大串中匹配字符的右側一個字符沒在子串中，大串移動步長= 整個串的距離 +1 如果大串中匹配范圍內的右側一個字符在子串中，大串移動距離= 子串長度 - 這個字符在子串中的位置 */ int *setCharStep(ch

14、ar *subStr) int *charStep=new intMAX_CHAR_SIZE; int subStrLen=strlen(subStr); for(int i=0;i<MAX_CHAR_SIZE;i+) charStepi=subStrLen+1; /從左向右掃描一遍 保存子串中每個字符所需移動步長 for(int i=0;i<subStrLen;i+) charStep(unsigned char)subStri =subStrLen-i; return charStep; /* 算法核心思想，從左向右匹配，遇到不匹配的看大串中匹配范圍之外的右側第一個字符在小串中

15、的最右位置 根據事先計算好的移動步長移動大串指針，直到匹配 */ 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_i<mainStrLen) /保存大串每次開始匹配的起始位置，便于移動指針 int tem=main_i; while(sub_j<subStrLen) if(mainStrmain_i = subStr

16、sub_j) main_i+; sub_j+; continue; else /如果匹配范圍外已經找不到右側第一個字符，則匹配失敗 if(tem+subStrLen > 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; r

17、eturn -1; int main() char *mainStr="absaddsasfasdfasdf" char *subStr="dd" int *charStep=setCharStep(subStr); cout<<"位置： "<<sundaySearch(mainStr,subStr,charStep)<<endl; system("pause"); return 0; /*華麗的分割線*/ 算法介紹以及實現(xiàn)偽碼： void preQsBc(char *x, in

18、t 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 += qs

19、Bcyj + m; /* shift */ / 第三個代碼實現(xiàn)，貌似比較高效 頭文件定義： /* Sunday.h */ class Sunday public: Sunday(); Sunday(); public: int find(const char* pattern, const char* text); private: void preCompute(const char* pattern); private: /Let's assume all characters are all ASCII static const int ASSIZE = 128; int _td

20、ASSIZE ; 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 c

21、har* 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

22、!= *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的實現(xiàn)。 需要說明的是strstr是c語言提

23、供的使用Brute Force實現(xiàn)的字符串匹配，簡單、通用是其最大的優(yōu)點。時間復雜度是O(mn) / 下面是Microsoft的實現(xiàn) /經典算法 /比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 &&