轉自：http://blog.csdn.net/zdl1016/archive/2009/10/11/4654061.aspx

?

?

我想說一句“我日，我討厭KMP！”。
KMP雖然經典，但是理解起來極其復雜，好不容易理解好了，便起碼來巨麻煩！
老子就是今天圖書館在寫了幾個小時才勉強寫了一個有bug的、效率不高的KMP，特別是計算next數組的部分。

其實，比KMP算法速度快的算法大把大把，而且理解起來更簡單，為何非要抓住KMP呢？筆試出現字符串模式匹配時直接上sunday算法，既簡單又高效，何樂而不為？
說實話，想到sunday算法的那個人，絕對是發散思維，絕對牛。當我在被KMP折磨的夠嗆的時候，我就琢磨，有沒有別的好算法呢？？琢磨了半天也沒想出個所以然來。笨啊，腦子不夠發散。

下面貼上一位兄弟寫的算法總結，很簡單（建議KMP部分就不用看了，看了費腦子）。
參見：http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html

趁著做Presentation的功夫，順便做一個總結

字符串匹配：

---willamette

在匹配串中尋找模式串是否出現，注意和最長公共子序列相區別(LCS: Longest Common Substring)

-：?Brute Force(BF或蠻力搜索)?算法：

這是世界上最簡單的算法了。
首先將匹配串和模式串左對齊，然后從左向右一個一個進行比較，如果不成功則模式串向右移動一個單位。

速度最慢。

那么，怎么改進呢？

我們注意到Brute Force?算法是每次移動一個單位，一個一個單位移動顯然太慢，是不是可以找到一些辦法，讓每次能夠讓模式串多移動一些位置呢？

當然是可以的。

我們也注意到，Brute Force?是很不intelligent?的，每次匹配不成功的時候，前面匹配成功的信息都被當作廢物丟棄了，當然，就如現在的變廢為寶一樣，我們也同樣可以將前面匹配成功的信息利用起來，極大地減少計算機的處理時間，節省成本。^_^

注意，蠻力搜索算法雖然速度慢，但其很通用，文章最后會有一些更多的關于蠻力搜索的信息。

-: KMP算法

首先介紹的就是KMP?算法。

原始論文：Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

這個算法實在是太有名了，大學上的算法課程除了最笨的Brute Force?算法，然后就介紹了KMP?算法。也難怪，呵呵。誰讓Knuth D.E.?這么world famous?呢，不僅拿了圖靈獎，而且還寫出了計算機界的Bible <The Art of Computer Programming>(?業內人士一般簡稱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算法

Horspool?算法。

當然，有市場就有競爭，字符串匹配這么大一個市場，不可能讓BF?和KMP?全部占了，于是又出現了幾個強勁的對手。

第一個登場的是

論文：Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

Horspool?算法的思想很簡單的。不過有個創新之處就是模式串是從右向左進行比較的。很好很強大，為后來的算法影響很大。

匹配串：abcbc?sdxzcxx

模式串：cbcac

這個時候我們從右向左進行對暗號，c-c?，恩對上了，第二個b-a?，不對啊，我們應該怎么辦？難道就這么放棄么。于是，模式串從不匹配的那個字符開始從右向左尋找匹配串中不匹配的字符b?的位置，結果發現居然有，趕快對上趕快對上，別耽誤了。

匹配串：abcbcsd?xzcxx

模式串：?cbcac

然后繼續從最右邊的字符從右向左進行比較。這時候，我們發現了，d-c?不匹配啊，而且模式穿里面沒有噢，沒辦法，只好移動一個模式串長度的單位了。

匹配串：abcbcsdxzcxx

模式串：??????cbcac

-：Boyer-Moore算法?

第二個上來的是Boyer-Moore?算法。

是一個很復雜的算法，當然，雖然理論上時間復雜度和KMP?差不多，但是實際上卻比KMP?快數倍，可見實踐是檢驗真理的唯一標準。

原始論文：R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977

分為兩步預處理，第一個是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?出現的時候，取移動距離最大的那個。
（
對于BM算法，好規則和壞規則，這里講的不夠明確，下面推薦一個講解非常優秀的文章，可謂圖文并茂啊，而且還是個MM寫的。
Boyer-Moore 經典單模式匹配算法
http://blog.csdn.net/iJuliet/archive/2009/05/19/4200771.aspx?
）

-：Sunday算法

最后一個是Sunday?算法，實際上比Boyer-Moore?還快，呵呵。長江后浪推前浪。

原始論文：Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

看原始論文的題目，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。

另外還有 字符串匹配自動機 后綴樹算法（分在線和非在線兩種）等 見如下文章。不能說那個比那個更好，各個算法都有自己的優勢及最佳應用場合。參考：
http://blog.csdn.net/yifan403/archive/2009/06/16/4272793.aspx?

另外，關于多模式字符串匹配 有AC算法（字符串匹配自動機思想） WM算法（BM在多模式的推廣應用）
參考：
http://blog.csdn.net/ijuliet/category/498465.aspx??該女子的blog有很多好文章。

/**********************華麗分割線******************************/
附上sunday代碼：
http://hi.baidu.com/kmj0217/blog/item/6f837f2f3da097311e3089cb.html?

一種比KMP?和?BM?更高效的匹配算法（如果想看原英文介紹，看下面分割線后的網址） 適用于：模式串較短的情況，最壞時間復雜性為O(N*M)，不過一般沒這么壞 Sunday 算法其實思想跟BM算法很相似，只不過Sunday算法是從前往后匹配，在匹配失敗時關注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒有 在匹配串中出現則直接跳過，即移動步長= 匹配串長度+ 1；否則，同BM算法一樣其移動步長=匹配串中最右端的該字符到末尾的距離+1。 ? 代碼如下： /* Sunday-字符串匹配算法?--?一種優于?KMP?的算法 思想類似于BM?算法，只不過是從左向右匹配 遇到不匹配的看大串中匹配范圍之外的右側第一個字符在小串中的最右位置 另外：采用BM/KMP?的預處理的做法，事先計算好移動步長?，等到遇到不匹配的值直接使用 */ #include<iostream> #include<string.h> using namespace std; //一個字符8位 最大256種 #define MAX_CHAR_SIZE 256 ? /*設定每個字符最右移動步長，保存每個字符的移動步長 如果大串中匹配字符的右側一個字符沒在子串中，大串移動步長=?整個串的距離+1 ?? 如果大串中匹配范圍內的右側一個字符在子串中，大串移動距離=?子串長度?-?這個字符在子串中的位置 */ int *setCharStep(char *subStr) { ???? int *charStep=new int[MAX_CHAR_SIZE]; ???? int subStrLen=strlen(subStr); ???? for(int i=0;i<MAX_CHAR_SIZE;i++) ???????????? charStep[i]=subStrLen+1; ???? //從左向右掃描一遍 保存子串中每個字符所需移動步長 ???? for(int i=0;i<subStrLen;i++) ???? { ????????????charStep[(unsigned char)subStr[i]?]=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_i<mainStrLen) ???? {?????????????????? ??????????? //保存大串每次開始匹配的起始位置，便于移動指針 ???????????? int tem=main_i; ???????????? while(sub_j<subStrLen) ???????????? { ??????????????????? if(mainStr[main_i] ==?? subStr[sub_j]) ??????????????????? { ??????????????????????????? main_i++; ??????????????????????????? sub_j++; ??????????????????????????? continue;??????????????????? ??????????????????? }???????????????? ??????????????????? else{ ????????????????????????//如果匹配范圍外已經找不到右側第一個字符，則匹配失敗 ???????????????????????? if(tem+subStrLen > mainStrLen) ???????????????????????????????????? return -1; ???????????????????????? //否則 移動步長 重新匹配 ???????????????????????? char firstRightChar=mainStr[tem+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) ????? qsBc[i] = m + 1; ?? for (i = 0; i < m; ++i) ????? qsBc[x[i]] = m - i; } void QS(char *x, int m, char *y, int n) { ?? int j, qsBc[ASIZE]; ?? /* Preprocessing */ ?? preQsBc(x, m, qsBc); ?? /* Searching */ ?? j = 0; ?? while (j <= n - m) { ????? if (memcmp(x, y + j, m) == 0) ???????? OUTPUT(j); ????? j += qsBc[y[j + m]];?????????????? /* shift */ ?? } }

// 第三個代碼實現，貌似比較高效
http://hi.baidu.com/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:
??? //Let's assume all characters are all ASCII
??? static const int ASSIZE = 128;
??? int _td[ASSIZE] ;
??? int _patLength;
??? int _textLength;
};


源文件
/* Sunday.cpp */

Sunday::Sunday()
{
}

Sunday::~Sunday()
{
}

void Sunday::preCompute(const char* pattern)
{
??? for(int i = 0; i < ASSIZE; i++ )?
??? ??? _td[i] = _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 += _td[tx[_patLength]];?
??? }
??? return -1;
}

簡單測試下：
int main()

{
??? char* text = "blog.csdn,blog.net";
??? 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);
}

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/whoismickey/archive/2009/02/08/3869367.aspx

strstr

glibc里的strstr函數用的是brute-force(naive)算法，它與其它算法的區別是strstr不對pattern(needle)進行預處理，所以用起來很方便。理論復雜度O (mn),?實際上，平均復雜度為O(n),?大部分情況下高度優化的算法性能要優于基于自動機的匹配算法，關于串匹配算法可參考http://www-igm.univ-mlv.fr/~lecroq/string/?。?glibc中使用了（1）Stephen R. van den Berg的實現，在他的基礎上，（2）Tor Myklebust?http://sources.redhat.com/ml/libc-alpha/2006-07/msg00028.html?給出了更復雜的實現，當然也更高效。 BF有一個重要性質是事先不用知道串的長度，而基于跳躍的算法是需要用字符串長度來判斷結束位置的。如何快速的確定字符串結束位置，可參考http://www.cppblog.com/ant/archive/2007/10/12/32886.html?，寫的很仔細。 將兩種思想結合起來，可以做出更快的strstr（3）。約定（1） 為strstrBerg; (2) 為strstrBergo，（3）為lstrstr，（4）為glibc中的strstr，簡單測試了一下： 從長度為2k的文本中查找長度為1、2、9的模式串，結果如下 1?????????????? 2????????????? 9 （1）0.000006 0.000006 0.000012??? （2）0.000007 0.000004 0.000008 （3）0.000002 0.000002 0.000005 （4）0.000005 0.000005 0.000011
下載strstr和測試程序?，?
下載后執行 :?
??????????? unzip testStrstr.zip
??????????? cd testStrstr
??????????? make test 基于sse2的strstr函數?是用sse2指令集對strstr的優化

轉載于:https://www.cnblogs.com/threef/archive/2013/04/02/2995664.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的(转)字符串匹配算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。