字符串匹配：
---willamette
在匹配串中尋找模式串是否出現(xiàn)，注意和最長(zhǎng)公共子序列相區(qū)別(LCS: Longest Common Substring)
最簡(jiǎn)單的Brute Force算法：
首先將匹配串和模式串左對(duì)齊，然后從左向右一個(gè)一個(gè)進(jìn)行比較，如果不成功則模式串向右移動(dòng)一個(gè)單位。
速度最慢。
那么，怎么改進(jìn)呢？
我們注意到Brute Force算法是每次移動(dòng)一個(gè)單位，一個(gè)一個(gè)單位移動(dòng)顯然太慢，是不是可以找到一些辦法，讓每次能夠讓模式串多移動(dòng)一些位置呢？
當(dāng)然是可以的。
我們也注意到，Brute Force是很不intelligent的，每次匹配不成功的時(shí)候，前面匹配成功的信息都被當(dāng)作廢物丟棄了，當(dāng)然，就如現(xiàn)在的變廢為寶一樣，我們也同樣可以將前面匹配成功的信息利用起來，極大地減少計(jì)算機(jī)的處理時(shí)間，節(jié)省成本。^_^
首先介紹的就是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.
這個(gè)算法實(shí)在是太有名了，大學(xué)上的算法課程除了最笨的Brute Force算法，然后就介紹了KMP算法。也難怪，呵呵。誰讓Knuth D.E.這么world famous呢，不僅拿了圖靈獎(jiǎng)，而且還寫出了計(jì)算機(jī)界的Bible <The Art of Computer Programming>(業(yè)內(nèi)人士一般簡(jiǎn)稱TAOCP).稍稍提一下，有個(gè)叫H.A.Simon的家伙，不僅拿了Turing Award，順手拿了個(gè)Nobel Economics Award，做了AI的爸爸，還是Chicago Univ的Politics PhD，可謂全才。
KMP的思想是這樣的：
利用不匹配字符的前面那一段字符的最長(zhǎng)前后綴來盡可能地跳過最大的距離
比如
模式串a(chǎn)babac這個(gè)時(shí)候我們發(fā)現(xiàn)在c處不匹配，然后我們看c前面那串字符串的最大相等前后綴，然后再來移動(dòng)
下面的兩個(gè)都是模式串，沒有寫出來匹配串
原始位置ababac
移動(dòng)之后 ababac
因?yàn)楹缶Y是已經(jīng)匹配了的，而前綴和后綴是相等的，所以直接把前綴移動(dòng)到原來后綴處，再?gòu)脑瓉淼腸處，也就是現(xiàn)在的第二個(gè)b處進(jìn)行比較。這就是KMP。
當(dāng)然，有市場(chǎng)就有競(jìng)爭(zhēng)，字符串匹配這么大一個(gè)市場(chǎng)，不可能讓BF和KMP全部占了，于是又出現(xiàn)了幾個(gè)強(qiáng)勁的對(duì)手。
第一個(gè)登場(chǎng)的是Horspool算法。
論文：Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506
Horspool算法的思想很簡(jiǎn)單的。不過有個(gè)創(chuàng)新之處就是模式串是從右向左進(jìn)行比較的。很好很強(qiáng)大，為后來的算法影響很大。
匹配串：abcbcsdxzcxx
模式串：cbcac
這個(gè)時(shí)候我們從右向左進(jìn)行對(duì)暗號(hào)，c-c，恩對(duì)上了，第二個(gè)b-a，不對(duì)啊，我們應(yīng)該怎么辦？難道就這么放棄么。于是，模式串從不匹配的那個(gè)字符開始從右向左尋找匹配串中不匹配的字符b的位置，結(jié)果發(fā)現(xiàn)居然有，趕快對(duì)上趕快對(duì)上，別耽誤了。
匹配串：abcbcsdxzcxx
模式串： cbcac
然后繼續(xù)從最右邊的字符從右向左進(jìn)行比較。這時(shí)候，我們發(fā)現(xiàn)了，d-c不匹配啊，而且模式穿里面沒有噢，沒辦法，只好移動(dòng)一個(gè)模式串長(zhǎng)度的單位了。
匹配串：abcbcsdxzcxx
模式串： cbcac
第二個(gè)上來的是Boyer-Moore算法。
是一個(gè)很復(fù)雜的算法，當(dāng)然，雖然理論上時(shí)間復(fù)雜度和KMP差不多，但是實(shí)際上卻比KMP快數(shù)倍，可見實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)。
原始論文：R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977
分為兩步預(yù)處理，第一個(gè)是bad-character heuristics，也就是當(dāng)出現(xiàn)錯(cuò)誤匹配的時(shí)候，移位，基本上就是做的Horspool那一套。
第二個(gè)就是good-suffix heuristics，當(dāng)出現(xiàn)錯(cuò)誤匹配的時(shí)候，我還要從不匹配點(diǎn)向左看啊，以前匹配的那段子字符串是不是在模式串本身中還有重復(fù)的啊，有重復(fù)的話，那么我就直接把重復(fù)的那段和匹配串中已經(jīng)匹配的那一段對(duì)齊就是了。再比較
匹配串：abaccbabbazz
模式串：cbadcba
我們看到已經(jīng)匹配好了cba，但是c-d不匹配，這個(gè)時(shí)候我們發(fā)現(xiàn)既可以采用bad-character heuristics，也可以使用good-suffix heuristics(模式串：cbadcba)，在這種情況下，邪不壓正。毅然投奔good。移動(dòng)得到
匹配串：abaccbabbazz
模式串： cbadcba
可是，我們有時(shí)候也發(fā)現(xiàn)，已經(jīng)匹配好的那一部分其實(shí)并沒有再有重復(fù)了的啊。這個(gè)時(shí)候，我們發(fā)現(xiàn)已經(jīng)匹配好的那串字符串有一部分在開頭重新出現(xiàn)了，那么，趕快，對(duì)齊吧。
匹配串：abacccbbbazz
模式串：cbadccb
然后得到
匹配串：abacccbbbazz
模式串： cbadccb
當(dāng)兩種Good-Suffix出現(xiàn)的時(shí)候，取移動(dòng)距離最大的那個(gè)。
最后一個(gè)是Sunday算法，實(shí)際上比Boyer-Moore還快，呵呵。長(zhǎng)江后浪推前浪。
原始論文：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兩位大牛似的。呵呵。不過實(shí)際上的確Sunday算法的確比BM算法要快，而且更簡(jiǎn)單。
Sunday的算法思想和Horspool有些相似，但是。當(dāng)出現(xiàn)不匹配的時(shí)候，卻不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右邊對(duì)齊的右一位的那個(gè)字符在模式串的位置。
比如：
匹配串：abcbczdxzc
模式串：zbcac
恩，這里我們看到b-a沒有對(duì)上，我們就看匹配串中的z在模式串的位置，然后，嘿嘿。
匹配串：abcbczdxzc
模式串： zbcac
如果模式串中的沒有那個(gè)字符怎么辦呢？很簡(jiǎn)單，跳過去唄。
匹配串：abcbcedxzcs
模式串：zbcac
e不在模式串中出現(xiàn)
那么我們就
匹配串：abcbcedxzcs
模式串： zbcac
實(shí)際上，現(xiàn)在還有很多很多字符串匹配算法，這里只是簡(jiǎn)單介紹了一下最常使用的五種算法，更多算法可以參考一下http://www.inf.fh-flensburg.de/lang/algorithmen/algo.htm，8過這個(gè)是德文網(wǎng)站，有的網(wǎng)頁(yè)沒有英文版的哦。