# ?????

我曾經(jīng)以不正確的姿勢學習研究了 KMP，但是被眾說紛紜文章搞頭腦迷糊了?？粗鴦e人撤了一堆的名詞術語，又是動態(tài)規(guī)劃，又是狀態(tài)圖，又是狀態(tài)轉換什么的，別人就是懂得多。感覺真是后悔學了中文，因為每個字我都懂，但就是不清楚別人在說什么??

我覺得 KMP 搜索算法應該有更好的學習姿勢，不需要扯概念扯術語，只需要直覺，Algorithm Visualizer 也許是一個可以在直覺上增加理解的好工具。

代碼倉庫可以通過以下鏈接或克隆獲?。?/p>

? ? git clone git@github.com:jimboyeah/jitter_search.git

? ? git clone https://github.com/jimboyeah/jitter_search.git

以上是學習庫 Algorithms.md 分類文檔中關于字符串搜索算法的部分，因為有離線整理資料的習慣，只會挑選部分公開發(fā)布。使用的工具是 Sublime Text + Git，感謝作者的共享軟件，真的非常高效。

# ?? Violent Search 暴力搜索算法

暴力搜索算法，Brute Force Searching，是兩層簡單的循環(huán)結構。先從 S 第 1 個字符位置開始逐字與 P 字符比較，發(fā)現(xiàn)不匹配時，再從 S 第 2 個字符位置開始逐字比較，依次處理直到整個 S 字符串處理完成，算法復雜度是 O(mn)。

輸出測試結果：

# ?? KMP Search

• - Algorithms 4th - 5.3 Substring Search

• - 有限狀態(tài)機之 KMP 字符匹配算法 https://labuladong.gitee.io/algo/3/27/99/

• - KMP - Algorithm Visualizer https://algorithm-visualizer.org/dynamic-programming/knuth-morris-pratts-string-search

• - 1143. 最長公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/

• - 14. 最長公共前綴 https://leetcode-cn.com/problems/longest-common-prefix/
  

KMP 字符串查找算法，用于在一個文本串 S 內(nèi)查找一個模式串 P 的出現(xiàn)位置，這個算法由 Donald Knuth、James H. Morris、Vaughan Pratt 三人于 1977 年聯(lián)合發(fā)表，故取這 3 人的姓氏命名此算法。

Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

暴力搜索算法中，是兩層簡單的循環(huán)結構。先從 S 第 1 個字符位置開始逐字與 P 字符比較，發(fā)現(xiàn)不匹配時，再從 S 第 2 個字符位置開始逐字比較，依次處理直到整個 S 字符串處理完成，算法復雜度是 O(mn)。

如果字符串中重復的字符比較多，或者 P 中有更合適的匹配位置卻沒有相應處理，該算法就顯得很蠢，比如如下數(shù)據(jù)：

? ? s = "shellllama" p = "llam"

KMP 算法的不同之處在于，它會花費空間來記錄一些信息，這是一處反饋機制，是動態(tài)規(guī)劃算法的特性，在上述情況中就會顯得很聰明。

相比暴力的逐字搜索，KMP 算法不用對 S 字符的每一個位置的字符串進行一輪比較，永不回退處理 S 輸入字符串。另一個角度來說，KMP 算法回退的是 PMT 查詢表的數(shù)據(jù)。

如果文本串的長度為 n，模式串的長度為 m，那么匹配過程的時間復雜度為 O(n)，整體時間復雜度為 O(m + n)。

而 KMP 算法通過引入一個前綴和后綴的公共字串長度表，也稱為部分匹配表 PMT - Partial Match Table，這個表的構建就是 KMP 算法的核心思想：監(jiān)測到不匹配時，P 提供足夠的信息來確定下一次應該從什么位置開始搜索。跳過一些不必要比較的字符串，從而提高了搜索效率，所以把構建出來的這個表稱作 next_table 或者 dp_table 都是合適的。

首先了解一些概念：

前綴：以第一個字符開始，但是不包含最后的字符，列如 "abc" 的前綴有 "a" 和 "ab"。

后綴：以最后的字符開始，但是不包含第一個字符，列如 "abc" 的后綴有 "c" 和 "bc"。

最長公共子串：Longest Common Substring 是指兩個字符串中最長連續(xù)相同的子串長度。 例如 “1AB2345CD” 和 “12345EF” 的最長公共子串為 “2345”，這也是一道算法題目。

子序列：由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

以 Algorithm Visualizer 演示的數(shù)據(jù)為例：

? ? S = "AAAABAABAAAABAAABAAAA";

? ? P = "AAAABAAA";

? ? S = "Monkey like banana.";

? ? P = "anana";

首先，KMP 需要根據(jù) P 生成一個 PMT 數(shù)據(jù)表，以供匹配失敗時確定下一個位置，PMT 生成規(guī)則，以前綴公共字串長度為例，PMT 每個值是 P 對應位置的匹配前綴字符數(shù)量，前綴長度，所以開始位置總是 0：

? ? PMT: 0 1 2 3 0 1 2 3? ? ? | Group

? ? ? P: A A A A B A A A? ? ? |? ?A

? ? PMT: 0 1 0 0? ? ? ? ? ? ? | Group

? ? ? P: l l a m? ? ? ? ? ? ? |? ?B

? ? PMT: 0 0 1 2? ? ? ? ? ? ? | Group

? ? ? P: n a n a? ? ? ? ? ? ? |? ?C

以上 A、B、C 三組數(shù)據(jù)產(chǎn)生的 PMT 如何使用呢？還是拿 P 去匹配 S 字符串，從頭開始，以 B 組數(shù)據(jù)為例：

? ? S: s h e l l l l a m a

? ? ? ?1 2 3 4 5 6 7 8 9 0

從 S 開頭檢索，直到位置 4 出現(xiàn)第一個匹配字符，繼續(xù)位置 5 出現(xiàn)第二個匹配字符。注意，每出現(xiàn)匹配表示 PMT 數(shù)據(jù)獲取的位置狀態(tài)也在變化。

檢索第 6 個字符時，出現(xiàn)不匹配，這時 PMT 的數(shù)據(jù)就起作用了。如果是 Violent Search 算法，肯定是推倒重來，從 S 的第 2 個字符開始檢索。但是 KMP 算法因為提前準備好了 PMT 數(shù)據(jù)，第一次出現(xiàn)不匹配時，知道可以從 PMT 表查詢到前面可以匹配的前綴長度，即上一個位置有一個目標前綴長度為 1 的匹配子串。

從而可以直接修改 PMT 狀態(tài)，或者叫做回退 PMT 數(shù)據(jù)指針位置，從而避免了在 S 字符串中進行回退操作。通常，輸入數(shù)據(jù)中 S 會比 P 大得多，之也就是 KMP 的算法優(yōu)點所在：高頻前綴字符串的優(yōu)化搜索算法。

# ?? Jitter Search

KMP 主要思想是當出現(xiàn)字符串不匹配時，可以通過 PMT 獲釋已經(jīng)匹配的前后綴長度，并利用這些長度信息避免從頭再去做匹配，考慮 PMT 查詢表的構建，KMP 本質上還是線性搜索算法。

實際上，KMP 算法并不比 C 庫函數(shù) strstr() 快多少，因為在缺少重復前綴后綴的情況下，KMP 算法并不占優(yōu)勢。

糟糕的情況是 P 長度 S 相近時，這種算法反而表現(xiàn)更差，花大力氣生成的 PMT 數(shù)據(jù)幾乎沒什么作用。

考慮到 KMP 算法的不足，這里設計了一種帶有二分法思維的搜索算法 Jitter Search：

- 第一步，在 S 串中找出所有 P 第一個字符出現(xiàn)的位置，設為 J 集合；

- 第二步，選擇一個整數(shù) jitter，比如 P 串長度的一半；

- 第三步，將 J 集合中所有位置偏移 jitter 處且與 P 串相應位置的值相同的過濾出來；

- 重復，這種操作，直到完整匹配結果。

這種算法的優(yōu)點是結合了二分法及低頻過濾器思維，可以高效處理非頻繁重復的字符串搜索。空間上需要占用一個 max(S, p) 的數(shù)組空間來存儲索引值。

以下為 Python 實現(xiàn)代碼，在應用中，可以對首字符高頻重復的情況做優(yōu)化：

輸出結構：

# ?? Sunday Search

• - 28. [Easy] implement strStr() https://leetcode-cn.com/problems/implement-strstr/

• - 187. [Medium] Repeated DNA Sequences https://leetcode.com/problems/repeated-dna-sequences/
  

1977 年，同時期德克薩斯大學 Robert S. Boyer 教授和 J Strother Moore 教授發(fā)明了一種新的字符串匹配算法，簡稱 BM 算法。該算法從模式串的尾部開始匹配，且最壞情況下的時間復雜度為 O(N)。在實踐中，比 KMP 從模式串的開頭開始匹配的算法效能高，但是這兩種算法都需要對 P 進行預處理，算法實現(xiàn)復雜，大大降低的實用性。

A fast string searching algorithm R. Boyer, J. S. Moore Published 1977 Computer Science Commun.

Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

但 BM 算法也還不是現(xiàn)有字符串查找算法中最快的算法，更快的查找算法是 Sunday 算法，由 Daniel M.Sunday 在 1990 年提出，它的思想跟 BM 算法很相似，只不過 Sunday 算法是從前往后匹配，邏輯如下：

? 從頭開始匹配，失敗時關注的是 S 文本串中按 P 匹配長度的下一位置的字符，記為 M；

??如果該字符不在模式串 P 中，這表示 M 位置之前不可能匹配，則下一輪匹配開始位置在偏移 len(P) 距離后；

??如果該字符出現(xiàn)在模式 P **最右側位置** Q 中，則將 Q 位置與 M 位置對齊后，再開始新一輪匹配搜索。

從右側檢索 P 中的字符位置這一點很關鍵，這可以保證對齊 S 序列中的 M 位置時不會錯失可能匹配的子串。

例如，以下一組數(shù)據(jù)：

? ? S = "aloong"

? ? P = "loon"

第一輪搜索 l:a 就不匹配，所以直接找到 len(P) 位置的 “n”，確認它在 P 串最右側的位置，字符索引位置按 0 為起始值：

? ? S = a l o o n g? ? ? ? >>>? ?S = a l o o n g

? ? ? ? ^? ? ? ?^M = 4? ? ?>>>? ? ? ? ?^? ? ?^M = 4

? ? P = l o o n? ? ? ? ? ? >>>? ?P =? ?l o o n?

? ? ? ? ^? ? ?^Q = 3? ? ? ?>>>? ? ? ? ?^? ? ?^Q = 3

然后，再按對齊后的序列進入第二輪搜索，如果 M 位置的字符沒有出現(xiàn)在 P 序列中，這種情況就是最好處理的，也是最有效率的，直接就只可以跳過一長段不可能匹配的子序列，大大提高的檢索效率。同時，與 KMP 等算法相比，還可以不事先建立索引表。

輸出結果：

Sunday 算法就像在移動一個匹配窗口，連續(xù)匹配時窗口就放大，匹配失敗就根據(jù) M 指示的字符來調整新窗口位置。實際上是對 BM 算法的優(yōu)化，并且它更簡單易實現(xiàn)。

Sunday 算法可以先對 P 建立查詢表，再對 S 進行搜索。那表時的掃描順序沒有限制，為了提高最壞情況下的算法效率，可以對 P 字符按照其出現(xiàn)的概率從小到大的順序掃描，這樣能盡早地確定失配與否。

Horspool 算法的思想有個創(chuàng)新之處就是模式串是從右向左進行比較的，在不匹配情況處理手法和 Sunday 有類似特征。

# ?? Tests for String Search

最后，是以上幾種字符串搜索算法的測試用例：