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

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

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

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

字符串匹配：

---willamette

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

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

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

速度最慢。

那么，怎么改進呢？

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

當然是可以的。

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

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

-: 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>(業(yè)內人士一般簡稱TAOCP).稍稍提一下，有個叫H.A.Simon的家伙，不僅拿了Turing Award，順手拿了個Nobel Economics Award，做了AI的爸爸，還是Chicago Univ的Politics PhD，可謂全才。

KMP的具體描述略去，教科書一大把。

-：Horspool算法

Horspool算法。

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

第一個登場的是

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

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

匹配串：abcbcsdxzcxx

模式串：cbcac

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

匹配串：abcbcsdxzcxx

模式串： cbcac

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

匹配串：abcbcsdxzcxx

模式串：      cbcac

-：Boyer-Moore算法

對于BM算法，下面推薦一個講解非常優(yōu)秀的文章，可謂圖文并茂啊，而且還是個MM寫的。

Boyer-Moore 經(jīng)典單模式匹配算法
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有些相似，但是。當出現(xiàn)不匹配的時候，卻不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右邊對齊的右一位的那個字符在模式串的位置。

比如：

匹配串：abcbczdxzc

模式串：zbcac

恩，這里我們看到b-a沒有對上，我們就看匹配串中的z在模式串的位置，然后，嘿嘿。

匹配串：abcbczdxzc

模式串：     zbcac

如果模式串中的沒有那個字符怎么辦呢？很簡單，跳過去唄。

匹配串：abcbcedxzcs

模式串：zbcac

e不在模式串中出現(xiàn)

那么我們就

匹配串：abcbcedxzcs

模式串：      zbcac

(2009/10/20補充)
RK算法

某一天在圖書館的一本算法分析設計書上翻到的。思路很新穎！和大家分享下。
在串匹配的簡單算法中，把文本每m個字符構成的字符段作為一個字段，和模式進行匹配檢查。如果能對一個長度為m的字符

串賦以一個Hash函數(shù)。那么顯然只有那些與模式具有相同hash函數(shù)值的文本中的字符串才有可能與模式匹配，這是必要條件

，而沒有必要去考慮文本中所有長度為m的字段，因而大大提高了串匹配的速度。因此RK算法的思想和KMP，BM，Sunday等思

路迥然不同！
（事實上，之前的串匹配方法，是將模式串的一個一個字符作為小的特征去分別進行匹配，而RK算法則是將串整體作為一個

特征！難就難在單個字符的特征很容易想得到，整體作為一個特征就沒那么容易想得到了）
如果把整體作為一個特征，那么如何快速的求出這個整體特征的特征值？？
模式串的特征值僅需求一次即可。對于文本中的任意m個字符構成的字串如何快速的求特征就是個難點了。
拋磚引玉，這里給出一個簡單的特征計算。 將字符串的每一個字符看做一個數(shù)，那么這個字符串的就是一個數(shù)字數(shù)組，通

過積分向量可以快速任意一個長度子字符串的向量和。可以把字符串的對應的字符數(shù)組的元素和看做這個字符串整體特征。

這個特征是可以再O（1）的時間內求出的。其實原始的RK算法里面是把字符串看做一個26進制數(shù)在計算特征的。這里就不啰

嗦了，有興趣的可以深入查找

aabseesds 模式串 ees
      ees

發(fā)現(xiàn) see向量和 == ees的向量和
然后就對see和ees做逐個字符的比較。發(fā)現(xiàn)不匹配繼續(xù)往下走
aabseesds 模式串 ees
        ees
發(fā)現(xiàn) ees向量和 == ees的向量和
然后就對ees和ees做逐個字符的比較。發(fā)現(xiàn)匹配OK。

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

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

===============================================================================
一個sunday算法的實現(xiàn)
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的實現(xiàn)。
需要說明的是strstr是c語言提供的使用Brute Force實現(xiàn)的字符串匹配，簡單、通用是其最大的優(yōu)點。時間復雜度是O(mn)
// 下面是Microsoft的實現(xiàn)
//經(jīng)典算法
//比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