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