字元串比對
字元串比對(String Matchiing)也稱字元串搜尋(String Searching)是字元串算法中重要的一種，是指從一個大字元串或文本中找到模式串出現的位置。
字元串比對概念
字元串比對問題的形式定義：
- 文本（Text）是一個長度為 n 的數組 T[1..n]；
- 模式（Pattern）是一個長度為 m 且 m≤n 的數組 P[1..m]；
- T 和 P 中的元素都屬于有限的字母表 Σ 表；
- 如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即對 1≤j≤m，有 T[s+j] = P[j]，則說模式 P 在文本 T 中出現且位移為 s，且稱 s 是一個有效位移（Valid Shift）。
比如上圖中，目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出現。該模式在此文本中僅出現一次，即在位移 s = 3 處，位移 s = 3 是有效位移。
字元串比對算法通常分為兩個步驟：預處理（Preprocessing）和比對（Matching）。是以算法的總運作時間為預處理和比對的時間的總和。
上圖描述了常見字元串比對算法的預處理和比對時間。
字元串比對算法
解決字元串比對的算法包括：樸素算法（Naive Algorithm） 即暴力破解、Rabin-Karp 算法、有限自動機算法（Finite Automation）、 Knuth-Morris-Pratt 算法（即 KMP Algorithm）、Boyer-Moore 算法、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法和 Sunday 算法等。
BF 算法
樸素的字元串比對算法（Naive String Matching Algorithm)
樸素的字元串比對算法又稱為暴力比對算法（Brute Force Algorithm），是最為簡單的字元串比對算法
在開始講解這個算法之前，我先定義兩個概念，友善我後面講解。它們分别是主串和模式串。這倆概念很好了解，我舉個例子你就懂了。
比方說，我們在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m。因為我們是在主串中查找模式串，是以n>m。
作為最簡單、最暴力的字元串比對算法，BF 算法的思想可以用一句話來概括，那就是，我們在主串中，檢查起始位置分别是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串比對的。我舉一個例子給你看看，你應該可以了解得更清楚。
從上面的算法思想和例子，我們可以看出，在極端情況下，比如主串是“aaaaa… aaaaaa”（省略号表示有很多重複的字元 a），模式串是“aaaaab”。我們每次都比對 m 個字元，要比對 n-m+1 次，是以，這種算法的最壞情況時間複雜度是 O(n*m)。
盡管理論上，BF 算法的時間複雜度很高，是 O(n*m)，但在實際的開發中，它卻是一個比較常用的字元串比對算法。為什麼這麼說呢？原因有兩點。
第一，實際的軟體開發中，大部分情況下，模式串和主串的長度都不會太長。而且每次模式串與主串中的子串比對的時候，當中途遇到不能比對的字元的時候，就可以就停止了，不需要把 m 個字元都比對一下。是以，盡管理論上的最壞情況時間複雜度是 O(n*m)，但是， 統計意義上，大部分情況下，算法執行效率要比這個高很多。
第二，樸素字元串比對算法思想簡單，代碼實作也非常簡單。簡單意味着不容易出錯，如果有 bug 也容易暴露和修複。在工程中，在滿足性能要求的前提下，簡單是首選。這也是我們常說的。
是以，在實際的軟體開發中，絕大部分情況下，樸素的字元串比對算法就夠用了。
RK 算法
RK 算法的全稱叫 Rabin-Karp 算法，是由它的兩位發明者 Rabin 和 Karp 的名字來命名的。這個算法了解起來也不是很難。我個人覺得，它其實就是剛剛講的 BF 算法的更新版。
RK 算法的全稱叫 Rabin-Karp 算法，是由它的兩位發明者 Rabin 和 Karp 的名字來命名的。這個算法了解起來也不是很難，它其實就是剛剛講的 BF 算法的更新版。
上面講 BF 算法的時候講過，如果模式串長度為 m，主串長度為 n，那在主串中，就會有n-m+1 個長度為 m 的子串，我們隻需要暴力地對比這 n-m+1 個子串與模式串，就可以找出主串與模式串比對的子串。
但是，每次檢查主串與子串是否比對，需要依次比對每個字元，是以 BF 算法的時間複雜度就比較高，是 O(n*m)。我們對樸素的字元串比對算法稍加改造，引入雜湊演算法，時間複雜度立刻就會降低。
RK 算法的思路是這樣的：我們通過雜湊演算法對主串中的 n-m+1 個子串分别求哈希值，然後逐個與模式串的哈希值比較大小。如果某個子串的哈希值與模式串相等，那就說明對應的子串和模式串比對了（這裡先不考慮哈希沖突的問題，後面我們會講到）。因為哈希值是一個數字，數字之間比較是否相等是非常快速的，是以模式串和子串比較的效率就提高了。
不過，通過雜湊演算法計算子串的哈希值的時候，我們需要周遊子串中的每個字元。盡管模式串與子串比較的效率提高了，但是，算法整體的效率并沒有提高。有沒有方法可以提高雜湊演算法計算子串哈希值的效率呢？
這就需要雜湊演算法設計得非常有技巧了。我們假設要比對的字元串的字元集中隻包含 K 個字元，我們可以用一個 K 進制數來表示一個子串，這個 K 進制數轉化成十進制數，作為子串的哈希值。表述起來有點抽象，我舉了一個例子，看完你應該就能懂了。
比如要處理的字元串隻包含 a～z 這 26 個小寫字母，那我們就用二十六進制來表示一個字元串。我們把 a～z 這 26 個字元映射到 0～25 這 26 個數字，a 就表示 0，b 就表示 1， 以此類推，z 表示 25。
在十進制的表示法中，一個數字的值是通過下面的方式計算出來的。對應到二十六進制，一個包含 a 到 z 這 26 個字元的字元串，計算哈希的時候，我們隻需要把進位從 10 改成 26 就可以。
這個雜湊演算法你應該看懂了吧？現在，為了友善解釋，在下面的講解中，我假設字元串中隻包含 a～z 這 26 個小寫字元，我們用二十六進制來表示一個字元串，對應的哈希值就是二十六進制數轉化成十進制的結果。
這種雜湊演算法有一個特點，在主串中，相鄰兩個子串的哈希值的計算公式有一定關系。我這有個個例子，你先找一下規律，再來看我後面的講解。
從這裡例子中，我們很容易就能得出這樣的規律：相鄰兩個子串 s[i-1] 和 s[i]（i 表示子串在主串中的起始位置，子串的長度都為 m），對應的哈希值計算公式有交集，也就是說， 我們可以使用 s[i-1] 的哈希值很快地計算出 s[i] 的哈希值。如果用公式表示的話，就是下面這個樣子：
不過，這裡有一個小細節需要注意，那就是 26^(m-1) 這部分的計算，我們可以通過查表的方法來提高效率。我們事先計算好 26^0、26^1、26^2……26^(m-1)，并且存儲在一個長度為 m 的數組中，公式中的“次方”就對應數組的下标。當我們需要計算 26 的 x 次方的時候，就可以從數組的下标為 x 的位置取值，直接使用，省去了計算的時間。
我們開頭的時候提過，RK 算法的效率要比 BF 算法高，現在，我們就來分析一下，RK 算法的時間複雜度到底是多少呢？
整個 RK 算法包含兩部分，計算子串哈希值和模式串哈希值與子串哈希值之間的比較。第一部分，我們前面也分析了，可以通過設計特殊的雜湊演算法，隻需要掃描一遍主串就能計算出所有子串的哈希值了，是以這部分的時間複雜度是 O(n)。
模式串哈希值與每個子串哈希值之間的比較的時間複雜度是 O(1)，總共需要比較 n-m+1 個子串的哈希值，是以，這部分的時間複雜度也是 O(n)。是以，RK 算法整體的時間複雜度就是 O(n)。
這裡還有一個問題就是，模式串很長，相應的主串中的子串也會很長，通過上面的雜湊演算法計算得到的哈希值就可能很大，如果超過了計算機中整型資料可以表示的範圍，那該如何解決呢？
剛剛我們設計的雜湊演算法是沒有散列沖突的，也就是說，一個字元串與一個二十六進制數一一對應，不同的字元串的哈希值肯定不一樣。因為我們是基于進制來表示一個字元串的，你可以類比成十進制、十六進制來思考一下。實際上，我們為了能将哈希值落在整型資料範圍内，可以犧牲一下，允許哈希沖突。這個時候雜湊演算法該如何設計呢？
雜湊演算法的設計方法有很多，我舉一個例子說明一下。假設字元串中隻包含 a～z 這 26 個英文字母，那我們每個字母對應一個數字，比如 a 對應 1，b 對應 2，以此類推，z 對應26。我們可以把字元串中每個字母對應的數字相加，最後得到的和作為哈希值。這種哈希 算法産生的哈希值的資料範圍就相對要小很多了。
不過，你也應該發現，這種雜湊演算法的哈希沖突機率也是挺高的。當然，我隻是舉了一個最簡單的設計方法，還有很多更加優化的方法，比如将每一個字母從小到大對應一個素數，而不是 1，2，3……這樣的自然數，這樣沖突的機率就會降低一些。
那現在新的問題來了。之前我們隻需要比較一下模式串和子串的哈希值，如果兩個值相等， 那這個子串就一定可以比對模式串。但是，當存在哈希沖突的時候，有可能存在這樣的情 況，子串和模式串的哈希值雖然是相同的，但是兩者本身并不比對。
實際上，解決方法很簡單。當我們發現一個子串的哈希值跟模式串的哈希值相等的時候，我們隻需要再對比一下子串和模式串本身就好了。當然，如果子串的哈希值與模式串的哈希值不相等，那對應的子串和模式串肯定也是不比對的，就不需要比對子串和模式串本身了。
是以，雜湊演算法的沖突機率要相對控制得低一些，如果存在大量沖突，就會導緻 RK 算法的時間複雜度退化，效率下降。極端情況下，如果存在大量的沖突，每次都要再對比子串和模式串本身，那時間複雜度就會退化成 O(n*m)。但也不要太悲觀，一般情況下，沖突不會很多，RK 算法的效率還是比 BF 算法高的。
KMP 算法
KMP 算法是根據三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字來命名的，算法
的全稱是 Knuth Morris Pratt 算法，簡稱為 KMP 算法。
KMP 算法的核心思想，跟上面講的 BM 算法非常相近。我們假設主串是 a，模式串是 b。在模式串與主串比對的過程中，當遇到不可比對的字元的時候，我們希望找到一些規 律，可以将模式串往後多滑動幾位，跳過那些肯定不會比對的情況。
還記得我們上面講到的好字尾和壞字元嗎？ U這裡我們可以類比一下，在模式串和主串匹 配的過程中，把不能比對的那個字元仍然叫作壞字元 ，把已經比對的那段字元串叫作好前 綴。
當遇到壞字元的時候，我們就要把模式串往後滑動，在滑動的過程中，隻要模式串和好字首 有上下重合，前面幾個字元的比較，就相當于拿好字首的字尾子串，跟模式串的字首子串在 比較。這個比較的過程能否更高效了呢？可以不用一個字元一個字元地比較了嗎？
KMP 算法就是在試圖尋找一種規律：在模式串和主串比對的過程中，當遇到壞字元後，對 于已經比對過的好字首，能否找到一種規律，将模式串一次性滑動很多位？
我們隻需要拿好字首本身，在它的字尾子串中，查找最長的那個可以跟好字首的字首子串匹 配的。假設最長的可比對的那部分字首子串是{v}，長度是 k。我們把模式串一次性往後滑 動 j-k 位，相當于，每次遇到壞字元的時候，我們就把 j 更新為 k，i 不變，然後繼續比較。
為了表述起來友善，我把好字首的所有字尾子串中，最長的可比對字首子串的那個字尾子 串，叫作最長可比對字尾子串 ；對應的字首子串，叫作最長可比對字首子串。
如何來求好字首的最長可比對字首和字尾子串呢？我發現，這個問題其實不涉及主串，隻需 要通過模式串本身就能求解。是以，我就在想，能不能事先預處理計算好，在模式串和主串 比對的過程中，直接拿過來就用呢？
類似 BM 算法中的 bc、suffix、prefix 數組，KMP 算法也可以提前建構一個數組，用來存 儲模式串中每個字首(這些字首都有可能是好字首)的最長可比對字首子串的結尾字元下 标。我們把這個數組定義為next 數組 ，很多書中還給這個數組起了一個名字，叫失效函數 (failure function)。
數組的下标是每個字首結尾字元下标，數組的值是這個字首的最長可以比對字首子串的結尾 字元下标。這句話有點拗口，我舉了一個例子，你一看應該就懂了。
有了 next 數組，我們很容易就可以實作 KMP 算法了。我先假設 next 數組已經計算好 了，先給出 KMP 算法的架構代碼。
// a, b 分别是主串和模式串； n, m 分别是主串和模式串的長度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到 a[i] 和 b[j]
j = next[j - 1] + 1; 8 }
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到比對模式串的了
return i - m + 1;
}
}
return -1;
} 失效函數計算方法
KMP 算法的基本原理講完了，我們現在來看最複雜的部分，也就是 next 數組是如何計算 出來的？
當然，我們可以用非常笨的方法，比如要計算下面這個模式串 b 的 next[4]，我們就把 b[0, 4] 的所有字尾子串，從長到短找出來，依次看看，是否能跟模式串的字首子串比對。很顯 然，這個方法也可以計算得到 next 數組，但是效率非常低。有沒有更加高效的方法呢？
這裡的處理非常有技巧，類似于動态規劃。不過，動态規劃我們在後面才會講到，是以，我 這裡換種方法解釋，也能讓你聽懂。
我們按照下标從小到大，依次計算 next 數組的值。當我們要計算 next[i] 的時候，前面的 next[0]，next[1]，……，next[i-1] 應該已經計算出來了。利用已經計算出來的 next 值， 我們是否可以快速推導出 next[i] 的值呢？
如果 next[i-1]=k-1，也就是說，子串 b[0, k-1] 是 b[0, i-1] 的最長可比對字首子串。如果 子串 b[0, k-1] 的下一個字元 b[k]，與 b[0, i-1] 的下一個字元 b[i] 比對，那子串 b[0, k] 就 是 b[0, i] 的最長可比對字首子串。是以，next[i] 等于 k。但是，如果 b[0, k-1] 的下一字 符 b[k] 跟 b[0, i-1] 的下一個字元 b[i] 不相等呢？這個時候就不能簡單地通過 next[i-1] 得 到 next[i] 了。這個時候該怎麼辦呢？
我們假設 b[0, i] 的最長可比對字尾子串是 b[r, i]。如果我們把最後一個字元去掉，那 b[r, i- 1] 肯定是 b[0, i-1] 的可比對字尾子串，但不一定是最長可比對字尾子串。是以，既然 b[0, i-1] 最長可比對字尾子串對應的模式串的字首子串的下一個字元并不等于 b[i]，那麼我們就 可以考察 b[0, i-1] 的次長可比對字尾子串 b[x, i-1] 對應的可比對字首子串 b[0, i-1-x] 的下 一個字元 b[i-x] 是否等于 b[i]。如果等于，那 b[x, i] 就是 b[0, i] 的最長可比對字尾子串。
可是，如何求得 b[0, i-1] 的次長可比對字尾子串呢？次長可比對字尾子串肯定被包含在最 長可比對字尾子串中，而最長可比對字尾子串又對應最長可比對字首子串 b[0, y]。于是， 查找 b[0, i-1] 的次長可比對字尾子串，這個問題就變成，查找 b[0, y] 的最長比對字尾子串 的問題了。
按照這個思路，我們可以考察完所有的 b[0, i-1] 的可比對字尾子串 b[y, i-1]，直到找到一 個可比對的字尾子串，它對應的字首子串的下一個字元等于 b[i]，那這個 b[y, i] 就是 b[0, i] 的最長可比對字尾子串。
前面我已經給出 KMP 算法的架構代碼了，現在我把這部分的代碼也寫出來了。這兩部分代 碼合在一起，就是整個 KMP 算法的代碼實作。
// b 表示模式串， m 表示模式串的長度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k]; 9 }
if (b[k + 1] == b[i]) { 11 ++k;
}
next[i] = k; 14 }
return next; 16 } KMP 算法深度剖析
KMP 算法的原理和實作方法我們就講完了，我們現在來分析一下 KMP 算法的時間、空間複雜 度是多少？
空間複雜度很容易分析，KMP 算法隻需要一個額外的 next 數組，數組的大小跟模式串相 同。是以空間複雜度是 O(m)，m 表示模式串的長度。
KMP 算法包含兩部分，第一部分是建構 next 數組，第二部分才是借助 next 數組比對。所 以，關于時間複雜度，我們要分别從這兩部分來分析。
我們先來分析第一部分的時間複雜度。
計算 next 數組的代碼中，第一層 for 循環中 i 從 1 到 m-1，也就是說，内部的代碼被執行 了 m-1 次。for 循環内部代碼有一個 while 循環，如果我們能知道每次 for 循環、while 循環平均執行的次數，假設是 k，那時間複雜度就是 O(k*m)。但是，while 循環執行的次 數不怎麼好統計，是以我們放棄這種分析方法。
我們可以找一些參照變量，i 和 k。i 從 1 開始一直增加到 m，而 k 并不是每次 for 循環都 會增加，是以，k 累積增加的值肯定小于 m。而 while 循環裡 k=next[k]，實際上是在減 小 k 的值，k 累積都沒有增加超過 m，是以 while 循環裡面 k=next[k] 總的執行次數也不 可能超過 m。是以，next 數組計算的時間複雜度是 O(m)。
我們再來分析第二部分的時間複雜度。分析的方法是類似的。
i 從 0 循環增長到 n-1，j 的增長量不可能超過 i，是以肯定小于 n。而 while 循環中的那條 語句 j=next[j-1]+1，不會讓 j 增長的，那有沒有可能讓 j 不變呢？也沒有可能。因為 next[j-1] 的值肯定小于 j-1，是以 while 循環中的這條語句實際上也是在讓 j 的值減少。而 j 總共增長的量都不會超過 n，那減少的量也不可能超過 n，是以 while 循環中的這條語句 總的執行次數也不會超過 n，是以這部分的時間複雜度是 O(n)。
是以，綜合兩部分的時間複雜度，KMP 算法的時間複雜度就是 O(m+n)。
小結
BM 算法有兩個規則，壞字元和好字尾。KMP 算法借鑒 BM 算法的思想，可以總結成好前 綴規則。這裡面最難懂的就是 next 數組的計算。如果用最笨的方法來計算，确實不難，但 是效率會比較低。是以，我講了一種類似動态規劃的方法，按照下标 i 從小到大，依次計算 next[i]，并且 next[i] 的計算通過前面已經計算出來的 next[0]，next[1]，……，next[i-1] 來推導。
KMP 算法的時間複雜度是 O(n+m)，不過它的分析過程稍微需要一點技巧，不那麼直覺， 你隻要看懂就好了，并不需要掌握，在我們平常的開發中，很少會有這麼難分析的代碼。