《数据结构》—— 串，KMP模式算法（转载）
本文內容轉載自：
KMP 算法（1）：如何理解 KMP
KMP 算法（2）：其細微之處
一：背景展開目錄
給定一個主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出現的位置，此即串的模式匹配問題。
Knuth-Morris-Pratt 算法（簡稱 KMP）是解決這一問題的常用算法之一，這個算法是由高德納（Donald Ervin Knuth）和沃恩 · 普拉特在 1974 年構思，同年詹姆斯 ·H· 莫里斯也獨立地設計出該算法，最終三人于 1977 年聯合發表。
在繼續下面的內容之前，有必要在這里介紹下兩個概念：真前綴 和 真后綴。
由上圖所得， "真前綴" 指除了自身以外，一個字符串的全部頭部組合；"真后綴" 指除了自身以外，一個字符串的全部尾部組合。（網上很多博客，應該說是幾乎所有的博客，也包括我以前寫的，都是 “前綴”。嚴格來說，“真前綴” 和“前綴”是不同的，既然不同，還是不要混為一談的好！）
二：樸素字符串匹配算法展開目錄
初遇串的模式匹配問題，我們腦海中的第一反應，就是樸素字符串匹配（即所謂的暴力匹配），代碼如下：
/* 字符串下標始于 0 */ int NaiveStringSearch(string S, string P) {int i = 0; // S 的下標int j = 0; // P 的下標int s_len = S.size();int p_len = P.size();while (i < s_len && j < p_len){if (S[i] == P[j]) // 若相等，都前進一步{i++;j++;}else // 不相等{i = i - j + 1;j = 0;}}if (j == p_len) // 匹配成功return i - j;return -1; }復制代碼暴力匹配的時間復雜度為O(nm)，其中n為 S 的長度，m為 P 的長度。很明顯，這樣的時間復雜度很難滿足我們的需求。
接下來進入正題：時間復雜度為Θ(n+m)的 KMP 算法。
三：KMP 字符串匹配算法展開目錄
3.1 算法流程展開目錄
以下摘自阮一峰的字符串匹配的 KMP 算法，并作稍微修改。
（1）
首先，主串 "BBC ABCDAB ABCDABCDABDE" 的第一個字符與模式串 "ABCDABD" 的第一個字符，進行比較。因為 B 與 A 不匹配，所以模式串后移一位。
（2）
因為 B 與 A 又不匹配，模式串再往后移。
（3）
就這樣，直到主串有一個字符，與模式串的第一個字符相同為止。
（4）
接著比較主串和模式串的下一個字符，還是相同。
（5）
直到主串有一個字符，與模式串對應的字符不相同為止。
（6）
這時，最自然的反應是，將模式串整個后移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把 "搜索位置" 移到已經比較過的位置，重比一遍。
（7）
一個基本事實是，當空格與 D 不匹配時，你其實是已經知道前面六個字符是 "ABCDAB"。KMP 算法的想法是，設法利用這個已知信息，不要把 "搜索位置" 移回已經比較過的位置，而是繼續把它向后移，這樣就提高了效率。
（8）
| 模式串 | A | B | C | D | A | B | D | '\0' |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
怎么做到這一點呢？可以針對模式串，設置一個跳轉數組int next[]，這個數組是怎么計算出來的，后面再介紹，這里只要會用就可以了。
（9）
已知空格與 D 不匹配時，前面六個字符 "ABCDAB" 是匹配的。根據跳轉數組可知，不匹配處 D 的 next 值為 2，因此接下來從模式串下標為 2 的位置開始匹配。
（10）
因為空格與Ｃ不匹配，C 處的 next 值為 0，因此接下來模式串從下標為 0 處開始匹配。
（11）
因為空格與 A 不匹配，此處 next 值為 - 1，表示模式串的第一個字符就不匹配，那么直接往后移一位。
（12）
逐位比較，直到發現 C 與 D 不匹配。于是，下一步從下標為 2 的地方開始匹配。
（13）
逐位比較，直到模式串的最后一位，發現完全匹配，于是搜索完成。
3.2 next 數組是如何求出的展開目錄
next 數組的求解基于 “真前綴” 和“真后綴”，即next[i]等于P[0]...P[i - 1]最長的相同真前后綴的長度（請暫時忽視 i 等于 0 時的情況，下面會有解釋）。我們依舊以上述的表格為例，為了方便閱讀，我復制在下方了。
| 模式串 | A | B | C | D | A | B | D | '\0' |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
（1）：i = 0，對于模式串的首字符，我們統一為next[0] = -1；
（2）：i = 1，前面的字符串為A，其最長相同真前后綴長度為 0，即next[1] = 0；
（3）：i = 2，前面的字符串為AB，其最長相同真前后綴長度為 0，即next[2] = 0；
（4）：i = 3，前面的字符串為ABC，其最長相同真前后綴長度為 0，即next[3] = 0；
（5）：i = 4，前面的字符串為ABCD，其最長相同真前后綴長度為 0，即next[4] = 0；
（6）：i = 5，前面的字符串為ABCDA，其最長相同真前后綴為A，即next[5] = 1；
（7）：i = 6，前面的字符串為ABCDAB，其最長相同真前后綴為AB，即next[6] = 2；
（8）：i = 7，前面的字符串為ABCDABD，其最長相同真前后綴長度為 0，即next[7] = 0。
那么，為什么根據最長相同真前后綴的長度就可以實現在不匹配情況下的跳轉呢？舉個代表性的例子：假如i = 6時不匹配，此時我們是知道其位置前的字符串為ABCDAB，仔細觀察這個字符串，首尾都有一個AB，既然在i = 6處的 D 不匹配，我們為何不直接把i = 2處的 C 拿過來繼續比較呢，因為都有一個AB啊，而這個AB就是ABCDAB的最長相同真前后綴，其長度 2 正好是跳轉的下標位置。
有的讀者可能存在疑問，若在i = 5時匹配失敗，按照我講解的思路，此時應該把i = 1處的字符拿過來繼續比較，但是這兩個位置的字符是一樣的啊，都是B，既然一樣，拿過來比較不就是無用功了么？其實不是我講解的有問題，也不是這個算法有問題，而是這個算法還未優化，關于這個問題在下面會詳細說明，不過建議讀者不要在這里糾結，跳過這個，下面你自然會恍然大悟。
思路如此簡單，接下來就是代碼實現了，如下：
/* P 為模式串，下標從 0 開始 */ void GetNext(string P, int next[]) {int p_len = P.size();int i = 0; // P 的下標int j = -1; next[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){i++;j++;next[i] = j;}elsej = next[j];} }復制代碼一臉懵逼，是不是。。。上述代碼就是用來求解模式串中每個位置的next[]值。
下面具體分析，我把代碼分為兩部分來講：
（1）：i 和 j 的作用是什么？
i 和 j 就像是兩個” 指針 “，一前一后，通過移動它們來找到最長的相同真前后綴。
（2）：if...else... 語句里做了什么？
假設 i 和 j 的位置如上圖，由next[i] = j得，也就是對于位置 i 來說，區段 [0, i - 1] 的最長相同真前后綴分別是 [0, j - 1] 和[i - j, i - 1]，即這兩區段內容相同。
按照算法流程，if (P[i] == P[j])，則i++; j++; next[i] = j;；若不等，則j = next[j]，見下圖：
next[j]代表 [0, j - 1] 區段中最長相同真前后綴的長度。如圖，用左側兩個橢圓來表示這個最長相同真前后綴，即這兩個橢圓代表的區段內容相同；同理，右側也有相同的兩個橢圓。所以 else 語句就是利用第一個橢圓和第四個橢圓內容相同來加快得到 [0, i - 1] 區段的相同真前后綴的長度。
細心的朋友會問 if 語句中j == -1存在的意義是何？第一，程序剛運行時，j 是被初始為 - 1，直接進行P[i] == P[j]判斷無疑會邊界溢出；第二，else 語句中j = next[j]，j 是不斷后退的，若 j 在后退中被賦值為 - 1（也就是j = next[0]），在P[i] == P[j]判斷也會邊界溢出。綜上兩點，其意義就是為了特殊邊界判斷。
四：完整代碼展開目錄
/*** * author : 劉毅（Limer）* date : 2017-03-05* mode : C++ */#include <iostream> #include <string>using namespace std;/* P 為模式串，下標從 0 開始 */ void GetNext(string P, int next[]) {int p_len = P.size();int i = 0; // P 的下標int j = -1; next[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){i++;j++;next[i] = j;}elsej = next[j];} }/* 在 S 中找到 P 第一次出現的位置 */ int KMP(string S, string P, int next[]) {GetNext(P, next);int i = 0; // S 的下標int j = 0; // P 的下標int s_len = S.size();int p_len = P.size();while (i < s_len && j < p_len){if (j == -1 || S[i] == P[j]) // P 的第一個字符不匹配或 S[i] == P[j]{i++;j++;}elsej = next[j]; // 當前字符匹配失敗，進行跳轉}if (j == p_len) // 匹配成功return i - j;return -1; }int main() {int next[100] = { 0 };cout << KMP("bbc abcdab abcdabcdabde", "abcdabd", next) << endl; // 15return 0; }復制代碼五：算法復雜度分析展開目錄
在GetNext()和KMP()中，我們觀察i 的移動，一直往前不回溯，所以它們所耗的時間都是線性的，兩者相加為
Θ(m+n)。KMP 算法的時間復雜度還是很穩定的。
平均時間復雜度為
Θ(m+n)。最好時間復雜度為
O(m+(n?m))=O(n)。它發生在主串和模式串字符都不相同的情況下，例如，主串為abcdefghijk，模式串為+-*/。最差時間復雜度為
O(m+n)。它發生在主串和模式串都為相同的字符的情況下，例如，主串為aaaaaaaaaaaaaaaaaaaaa，模式串為aaaa。
六：KMP 優化展開目錄
| 模式串 | A | B | C | D | A | B | D | '\0' |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
以 3.2 的表格為例（已復制在上方），若在i = 5時匹配失敗，按照 3.2 的代碼，此時應該把i = 1處的字符拿過來繼續比較，但是這兩個位置的字符是一樣的，都是B，既然一樣，拿過來比較不就是無用功了么？這我在 3.2 已經解釋過，之所以會這樣是因為 KMP 不夠完美。那怎么改寫代碼就可以解決這個問題呢？很簡單。
/* P 為模式串，下標從 0 開始 */ void GetNextval(string P, int nextval[]) {int p_len = P.size();int i = 0; // P 的下標int j = -1; nextval[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){i++;j++;if (P[i] != P[j])nextval[i] = j;elsenextval[i] = nextval[j]; // 既然相同就繼續往前找真前綴}elsej = nextval[j];} }復制代碼在此也給各位讀者提個醒，KMP 算法嚴格來說分為 KMP 算法（未優化版）和 KMP 算法（優化版），所以建議讀者在表述 KMP 算法時，最好告知你的版本，因為兩者在某些情況下區別很大，這里簡單說下。
KMP 算法（未優化版）： next 數組表示最長的相同真前后綴的長度，我們不僅可以利用 next 來解決模式串的匹配問題，也可以用來解決類似字符串重復問題等等，這類問題大家可以在各大 OJ 找到，這里不作過多表述。
KMP 算法（優化版）： 根據代碼很容易知道（名稱也改為了 nextval），優化后的 next 僅僅表示相同真前后綴的長度，但不一定是最長（我個人稱之為 “最優相同真前后綴”）。此時我們利用優化后的 next 可以在模式串匹配問題中以更快的速度得到我們的答案（相較于未優化版），但是上述所說的字符串重復問題，優化版本則束手無策。
所以，該采用哪個版本，取決于你在現實中遇到的實際問題。
一：起始下標之 “爭”：0 和 1展開目錄
/* P 為模式串，下標從 0 開始 */ void GetNext(string P, int next[]) {int p_len = P.size();int i = 0; // P 的下標int j = -1; // 相同真前后綴的長度next[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){i++;j++;next[i] = j;}elsej = next[j];} }/* 在 S 中找到 P 第一次出現的位置 */ int KMP(string S, string P, int next[]) {GetNext(P, next);int i = 0; // S 的下標int j = 0; // P 的下標int s_len = S.size();int p_len = P.size();while (i < s_len && j < p_len){if (j == -1 || S[i] == P[j]) // P 的第一個字符不匹配或 S[i] == P[j]{i++;j++;}elsej = next[j]; // 當前字符匹配失敗，進行跳轉}if (j == p_len) // 匹配成功return i - j;return -1; }復制代碼上述代碼的起始下標都是從 0 開始的，但每個人對數組起始位置的編碼習慣不同，分為兩類：0 和 1。對于上面的代碼，起始位置如果改為 1 的話又是怎樣呢？
但它們的區別并不止如此。我們知道，KMP 算法的 next[i] 表示最長的相同真前后綴，但這對起始位置為 1 的 next[i] 卻不再適用。
| 模式串 | A | B | C | D | A | B | D | '\0' |
| next[i] | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
| 模式串 | A | B | C | D | A | B | D | '\0' |
| next[i] | 0 | 1 | 1 | 1 | 1 | 2 | 3 | 1 |
上面兩個表格表展示的是：相同模式串下不同起始位置的 next 值對比。
相比之下，起始位置為 1 的 next 值比起始位置為 0 的 next 值多了 1。多 1，不是巧合，而是必然。這很容易證明。
在 GetNext() 中，j 從 0 開始（起始位置為 1），在走了相等步后停下依次賦值給 next[i]，因此相較于起始位置為 0 的 next 總是多 1。這又引起了我們的思考，多了 1 后在模式匹配中，next 還會正確的實現跳轉么？當然會了，next 多 1，同時模式串的起始位置也多了 1，這就好比數學中，從 a=b 轉化為 a+1=b+1，形式不同但完全等價。
二：next[i] 里最不起眼處的妙用展開目錄
先來看一個問題，在主串 S 中找到模式串 P 所有可以完全匹配的位置。
很簡單，典型的 KMP 模式匹配。
假設起始位置都是從 0 開始，對于上圖，若已找到主串的第一個完全匹配位置即 0--4，那么請問接下來模式串如何移動？
不知道各位讀者有沒有注意過模式串最后末尾處的 next 值代表什么？（末尾即為字符串的結尾標志：'\0'）
它代表整個模式串的最長相同真前后綴。
利用這個 next 值，我們直接可以實現跳轉，更快地找到下一個匹配點。
總結
以上是生活随笔為你收集整理的《数据结构》—— 串，KMP模式算法（转载）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Windows中添加自己的程序到开机启动
- 下一篇： gradle 构建包含源码配置