字符串匹配：
---willamette
在匹配串中尋找模式串是否出現，注意和最長公共子序列相區別(LCS: Longest Common Substring)
最簡單的Brute Force算法：
首先將匹配串和模式串左對齊，然后從左向右一個一個進行比較，如果不成功則模式串向右移動一個單位。
速度最慢。
那么，怎么改進呢？
我們注意到Brute Force算法是每次移動一個單位，一個一個單位移動顯然太慢，是不是可以找到一些辦法，讓每次能夠讓模式串多移動一些位置呢？
當然是可以的。
我們也注意到，Brute Force是很不intelligent的，每次匹配不成功的時候，前面匹配成功的信息都被當作廢物丟棄了，當然，就如現在的變廢為寶一樣，我們也同樣可以將前面匹配成功的信息利用起來，極大地減少計算機的處理時間，節省成本。^_^
首先介紹的就是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前面那串字符串的最大相等前后綴，然后再來移動
下面的兩個都是模式串，沒有寫出來匹配串
原始位置ababac
移動之后 ababac
因為后綴是已經匹配了的，而前綴和后綴是相等的，所以直接把前綴移動到原來后綴處，再從原來的c處，也就是現在的第二個b處進行比較。這就是KMP。
當然，有市場就有競爭，字符串匹配這么大一個市場，不可能讓BF和KMP全部占了，于是又出現了幾個強勁的對手。
第一個登場的是Horspool算法。
論文：Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506
Horspool算法的思想很簡單的。不過有個創新之處就是模式串是從右向左進行比較的。很好很強大，為后來的算法影響很大。
匹配串：abcbcsdxzcxx
模式串：cbcac
這個時候我們從右向左進行對暗號，c-c，恩對上了，第二個b-a，不對啊，我們應該怎么辦？難道就這么放棄么。于是，模式串從不匹配的那個字符開始從右向左尋找匹配串中不匹配的字符b的位置，結果發現居然有，趕快對上趕快對上，別耽誤了。
匹配串：abcbcsdxzcxx
模式串： cbcac
然后繼續從最右邊的字符從右向左進行比較。這時候，我們發現了，d-c不匹配啊，而且模式穿里面沒有噢，沒辦法，只好移動一個模式串長度的單位了。
匹配串：abcbcsdxzcxx
模式串： cbcac
第二個上來的是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，當出現錯誤匹配的時候，我還要從不匹配點向左看啊，以前匹配的那段子字符串是不是在模式串本身中還有重復的啊，有重復的話，那么我就直接把重復的那段和匹配串中已經匹配的那一段對齊就是了。再比較
匹配串：abaccbabbazz
模式串：cbadcba
我們看到已經匹配好了cba，但是c-d不匹配，這個時候我們發現既可以采用bad-character heuristics，也可以使用good-suffix heuristics(模式串：cbadcba)，在這種情況下，邪不壓正。毅然投奔good。移動得到
匹配串：abaccbabbazz
模式串： cbadcba
可是，我們有時候也發現，已經匹配好的那一部分其實并沒有再有重復了的啊。這個時候，我們發現已經匹配好的那串字符串有一部分在開頭重新出現了，那么，趕快，對齊吧。
匹配串：abacccbbbazz
模式串：cbadccb
然后得到
匹配串：abacccbbbazz
模式串： cbadccb
當兩種Good-Suffix出現的時候，取移動距離最大的那個。
最后一個是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有些相似，但是。當出現不匹配的時候，卻不是去找匹配串中不匹配的字符在模式串的位置，而是直接找最右邊對齊的右一位的那個字符在模式串的位置。
比如：
匹配串：abcbczdxzc
模式串：zbcac
恩，這里我們看到b-a沒有對上，我們就看匹配串中的z在模式串的位置，然后，嘿嘿。
匹配串：abcbczdxzc
模式串： zbcac
如果模式串中的沒有那個字符怎么辦呢？很簡單，跳過去唄。
匹配串：abcbcedxzcs
模式串：zbcac
e不在模式串中出現
那么我們就
匹配串：abcbcedxzcs
模式串： zbcac
實際上，現在還有很多很多字符串匹配算法，這里只是簡單介紹了一下最常使用的五種算法，更多算法可以參考一下http://www.inf.fh-flensburg.de/lang/algorithmen/algo.htm，8過這個是德文網站，有的網頁沒有英文版的哦。