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