字符串匹配算法很多，
- 單模式串匹配的算法，也就是一個串跟一個串進行匹配。
兩種比較簡單的、好理解的，它們是：BF 算法和 RK 算法；
兩種比較難理解、但更加高效的，它們是：BM 算法和 KMP 算法； - 多模式串匹配算法，也就是在一個串中同時查找多個串。
包括 Trie 樹和 AC 自動機。
BF 算法（Brute Force）
BF 算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配算法，也叫樸素匹配算法。
比方說，我們在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m。因為我們是在主串中查找模式串，所以 n>m。
BF 算法的思想可以用一句話來概括，那就是，我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。
時間復(fù)雜度也比較高，是 O(n*m)。
不過，在實際的軟件開發(fā)中，因為這種算法實現(xiàn)簡單，對于處理小規(guī)模的字符串匹配很好用。
RK 算法（Rabin-Karp）
RK 算法的全稱叫 Rabin-Karp 算法，是由它的兩位發(fā)明者 Rabin 和 Karp 的名字來命名的。
RK 算法是 BF 算法的改進，它巧妙借助了我們前面講過的哈希算法，讓匹配的效率有了很大的提升。
RK 算法的思路是這樣的：
我們通過哈希算法對主串中的 n-m+1 個子串分別求哈希值，然后逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相等，那就說明對應(yīng)的子串和模式串匹配了（這里先不考慮哈希沖突的問題，后面我們會講到）。因為哈希值是一個數(shù)字，數(shù)字之間比較是否相等是非常快速的，所以模式串和子串比較的效率就提高了。
這就需要哈希算法設(shè)計的非常有技巧了。我們假設(shè)要匹配的字符串的字符集中只包含 K 個字符，我們可以用一個 K 進制數(shù)來表示一個子串，這個 K 進制數(shù)轉(zhuǎn)化成十進制數(shù)，作為子串的哈希值。
理想情況下，RK 算法的時間復(fù)雜度是 O(n)，跟 BF 算法相比，效率提高了很多。不過這樣的效率取決于哈希算法的設(shè)計方法，如果存在沖突的情況下，時間復(fù)雜度可能會退化。極端情況下，哈希算法大量沖突，時間復(fù)雜度就退化為 O(n*m)。
BM算法（Boyer-Moore）
BM（Boyer-Moore）算法。它是一種非常高效的字符串匹配算法，有實驗統(tǒng)計，它的性能是著名的KMP 算法的 3 到 4 倍。BM 算法的原理很復(fù)雜，比較難懂，學起來會比較燒腦。
BM 算法的核心思想
在模式串與主串匹配的過程中，當模式串和主串某個字符不匹配的時候，能夠跳過一些肯定不會匹配的情況，將模式串往后多滑動幾位。
BM 算法原理分析
BM 算法包含兩部分，分別是壞字符規(guī)則（bad character rule）和好后綴規(guī)則（good suffix shift）。
1. 壞字符規(guī)則
BM 算法的匹配順序比較特別，它是按照模式串下標從大到小的順序，倒著匹配的。
從模式串的末尾往前倒著匹配，當我們發(fā)現(xiàn)某個字符沒法匹配的時候。我們把這個沒有匹配的字符叫作壞字符（主串中的字符）。比如此處的c。
當發(fā)生不匹配的時候，我們把壞字符對應(yīng)的模式串中的字符下標記作 si。如果壞字符在模式串中存在，我們把這個壞字符在模式串中的下標記作 xi。如果不存在，我們把 xi 記作 -1。那模式串往后移動的位數(shù)就等于 si-xi。（注意，我這里說的下標，都是字符在模式串的下標）。
特別說明一點，如果壞字符在模式串里多處出現(xiàn)，那我們在計算 xi 的時候，選擇最靠后的那個，因為這樣不會讓模式串滑動過多，導(dǎo)致本來可能匹配的情況被滑動略過。
2. 好后綴規(guī)則
我們把已經(jīng)匹配的 bc 叫作好后綴，記作{u}。我們拿它在模式串中查找，如果找到了另一個跟{u}相匹配的子串{u}，那我們就將模式串滑動到子串{u}與主串中{u}對齊的位置。
如果在模式串中找不到另一個等于{u}的子串，我們就直接將模式串，滑動到主串中{u}的后面。
如果好后綴在模式串中不存在可匹配的子串，那在我們一步一步往后滑動模式串的過程中，只要主串中的{u}與模式串有重合，那肯定就無法完全匹配。但是當模式串滑動到前綴與主串中{u}的后綴有部分重合的時候，并且重合的部分相等的時候，就有可能會存在完全匹配的情況。
所以，針對這種情況，我們不僅要看好后綴在模式串中，是否有另一個匹配的子串，我們還要考察好后綴的后綴子串，是否存在跟模式串的前綴子串匹配的。
3. 壞字符/好后綴 如何選擇
當模式串和主串中的某個字符不匹配的時候，如何選擇用好后綴規(guī)則還是壞字符規(guī)則，來計算模式串往后滑動的位數(shù)？
我們可以分別計算好后綴和壞字符往后滑動的位數(shù)，然后取兩個數(shù)中最大的，作為模式串往后滑動的位數(shù)。這種處理方法還可以避免我們前面提到的，根據(jù)壞字符規(guī)則，計算得到的往后滑動的位數(shù)，有可能是負數(shù)的情況。
BM 算法代碼實現(xiàn)
BM 算法的性能分析及優(yōu)化
實際上，BM 算法的時間復(fù)雜度分析起來是非常復(fù)雜，這篇論文“A new proof of the linearity of the Boyer-Moore string searching algorithm”證明了在最壞情況下，BM 算法的比較次數(shù)上限是 5n。這篇論文“Tight bounds on the complexity of the Boyer-Moore string matching algorithm”證明了在最壞情況下，BM 算法的比較次數(shù)上限是 3n。你可以自己閱讀看看。
BM 算法總結(jié)
BM 算法核心思想是，利用模式串本身的特點，在模式串中某個字符與主串不能匹配的時候，將模式串往后多滑動幾位，以此來減少不必要的字符比較，提高匹配的效率。BM 算法構(gòu)建的規(guī)則有兩類，壞字符規(guī)則和好后綴規(guī)則。好后綴規(guī)則可以獨立于壞字符規(guī)則使用。因為壞字符規(guī)則的實現(xiàn)比較耗內(nèi)存，為了節(jié)省內(nèi)存，我們可以只用好后綴規(guī)則來實現(xiàn) BM 算法。
KMP算法（Knuth Morris Pratt）
KMP 算法是根據(jù)三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字來命名的，算法的全稱是 Knuth Morris Pratt 算法，簡稱為 KMP 算法。
KMP 算法的核心思想，跟前面的 BM 算法非常相近。
我們假設(shè)主串是 a，模式串是 b。在模式串與主串匹配的過程中，當遇到不可匹配的字符的時候，我們希望找到一些規(guī)律，可以將模式串往后多滑動幾位，跳過那些肯定不會匹配的情況。
在模式串和主串匹配的過程中，把不能匹配的那個字符仍然叫作壞字符，把已經(jīng)匹配的那段字符串叫作好前綴。
當遇到壞字符的時候，我們就要把模式串往后滑動，在滑動的過程中，只要模式串和好前綴有上下重合，前面幾個字符的比較，就相當于拿好前綴的后綴子串，跟模式串的前綴子串在比較。這個比較的過程能否更高效了呢？可以不用一個字符一個字符地比較了嗎？
KMP 算法就是在試圖尋找一種規(guī)律：在模式串和主串匹配的過程中，當遇到壞字符后，對于已經(jīng)比對過的好前綴，能否找到一種規(guī)律，將模式串一次性滑動很多位？
我們只需要拿好前綴本身，在它的后綴子串中，查找最長的那個可以跟好前綴的前綴子串匹配的。假設(shè)最長的可匹配的那部分前綴子串是{v}，長度是 k。我們把模式串一次性往后滑動 j-k 位，相當于，每次遇到壞字符的時候，我們就把 j 更新為 k（前面k位是好前綴的前綴字串{v}），i 不變，然后繼續(xù)比較。
next 數(shù)組各值的含義：代表當前字符之前的字符串中，有多大長度的相同前綴/后綴。
例如next [j] = k，代表j 之前的字符串中有最大長度為k 的相同前綴后綴。
匹配失配，j = next [j]，模式串向右移動的位數(shù)為：j - next[j]。
換言之，當模式串的后綴Pj-k Pj-k+1, ..., Pj-1 跟文本串Si-k Si-k+1, ..., Si-1匹配成功，但Pj 跟Si匹配失敗時，因為next[j] = k，相當于在不包含pj的模式串中有最大長度為k 的相同前綴后綴，即P0 P1 ...Pk-1 = Pj-k Pj-k+1...Pj-1，故令j = next[j]，從而讓模式串右移j - next[j] 位，使得模式串的前綴P0 P1, ..., Pk-1對應(yīng)著文本串 Si-k Si-k+1, ..., Si-1，而后讓Pk 跟Si 繼續(xù)匹配。如下圖所示：
當匹配失敗時，j要移動的下一個位置k。存在著這樣的性質(zhì)：最前面的k個字符和j之前的最后k個字符是一樣的。
如果用數(shù)學公式來表示是這樣的 P[0 ~ k-1] == P[j-k ~ j-1]，如下圖：
弄明白了這個就應(yīng)該可能明白為什么可以直接將j移動到k位置了。
因為:
當T[i] != P[j]時
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
...[待補充]
極客時間--數(shù)據(jù)結(jié)構(gòu)與算法之美--32 | 字符串匹配基礎(chǔ)（上）：如何借助哈希算法實現(xiàn)高效字符串匹配？
極客時間--數(shù)據(jù)結(jié)構(gòu)與算法之美--33 | 字符串匹配基礎(chǔ)（中）：如何實現(xiàn)文本編輯器中的查找功能？
極客時間--數(shù)據(jù)結(jié)構(gòu)與算法之美--34 | 字符串匹配基礎(chǔ)（下）：如何借助BM算法輕松理解KMP算法？
KMP算法詳解-徹底清楚了(轉(zhuǎn)載+部分原創(chuàng))
從頭到尾徹底理解KMP（2014年8月22日版）
