字符串匹配的 KMP算法
一般字符串匹配過程
KMP算法是字符串匹配算法的一種改進版，一般的字符串匹配算法是：從主串(目標字符串)和模式串(待匹配字符串)的第一個字符開始比較，如果相等則繼續匹配下一個字符， 如果不相等則從主串的下一個字符開始匹配，直到模式串被匹配完，則匹配成功，或主串被匹配完且模式串未匹配完，則匹配失敗。匹配過程入下圖：
這種實現方式是最簡單的， 但也是低效的，因為第三次匹配結束后的第四次和第五次是沒有必要的。
分析
第三次匹配在j = 0(a)和i = 2(a)處開始，在j = 4(c)和i = 6(b)處失敗，這意味著模式串和主串中：j = 0(a)和i = 2(a)、j = 1(b)和i = 3(b)、j = 2(c)和i = 4(c)、j = 3(a)和i = 5(a)這四個字符相互匹配。
分析模式串的前3個字符：模式串的第一個字符j = 0是a，j = 1(b)、j = 2(c)這兩個字符和j = 0(a)不同，因此以這兩個字符開頭的匹配必定失敗，在第三次匹配中，主串中i = 3(b)、i = 4(c)和模式串j = 1(b)、j = 2(c)相互匹配，因此匹配失敗后，可以直接跳過主串中i = 3(b)、i = 4(c)這兩個字符的匹配。
繼續分析模式串的j = 3(a)和j = 4(c)這兩個字符，如果模式串匹配到j = 4(c)這個字符才失敗的話，因為j = 4(c)的前一個字符j = 3(a)和第一個字符j = 0(a)是相同的，結合上一個分析得知：
1)：下一次匹配中主串已經跳過了和
j = 3(a)前兩個相互匹配的字符i = 3(b)、i = 4(c)，將從i = 5(a)開始匹配。
2)：j = 3(a)和i = 5(a)相互匹配。
因此下一次匹配認為j = 3(a)和i = 5(a)已經匹配過了，匹配從j = 4(b)和i = 6(b)開始，這樣的話也跳過了j = 3(a)這個字符的匹配。
同理可得第二次匹配也是沒必要的。
KMP算法
KMP算法匹配過程
利用KMP算法匹配的過程如下圖：
KMP算法的改進之處在于：能夠知道在匹配失敗后，有多少字符是不需要進行匹配可以直接跳過的，匹配失敗后，下一次匹配從什么地方開始能夠有效的減少不必要的匹配過程。
next[n]求解方法
由上面的分析可以發現，KMP算法的核心在于對模式串本身的分析，其分析結果能提供在j = n位置匹配失敗時，從j = 0到j = n - 1這個子串中前綴和后綴的最長公共匹配的字符數，這樣說可能比較難以理解，看下圖：
在得到子串前綴和后綴的最長公共匹配字符數l后，以后在i = x,j = n處匹配失敗時，可以直接從i = x,j = l處繼續匹配(證明過程參考:嚴蔚敏的《數據結構》4.3章)，這樣問題就很明顯了，我們要求出n和l對應的值，其中n是模式串字符數組的下標，l的有序集合通常稱之為next數組，前面兩個模式串的next數組和下標n的對應如下：
模式串2完整匹配過程
有了這個next數組，那么在匹配的過程中我們就能在j = n處匹配失敗后，根據next[n]的值進行偏移，其中next[0]固定為-1，代表在當前i這個位置整個模式串和主串都無法匹配成功，要從下一個位置i = i + 1及j = 0處開始匹配，模式串2的匹配過程如下：
現在知道了next數組的作用，也知道在有next數組時的匹配過程，那么剩下的問題就是如何通過代碼求出next數組及匹配過程了。
求
next數組的過程可以認為是將模式串拆分成n個子串，分別對每個子串求前綴和后綴的最長公共匹配字符數l，這一點可以通過上圖(最長公共匹配字符數)看出來(沒有畫出l=0時的圖解)看出來。
代碼實現
求next數組的代碼如下：
1 void get_next(string pattern, int next[]) { 2 // ！！！！！！！！！！由網友(評論第一條)指出該算法存在問題，已將有問題的代碼注釋并附上臨時想到的算法代碼。 3 4 // int i = 0; // i用來記錄當前計算的next數組元素的下標， 同時也作為模式串本身被匹配到的位置的下標 5 // int j = 0; // j == -1 代表從在i的位置模式串無法匹配成功，從下一個位置開始匹配 6 // next[0] = -1; // next[0]固定為-1 7 // int p_len = pattern.length(); 8 // while (++i < p_len) { 9 // if (pattern[i] == pattern[j]) { 10 // // j是用來記錄當前模式串匹配到的位置的下標， 這就意味著當j = l時， 11 // // 則在pattern[j]這個字符前面已經有l - 1個成功匹配, 12 // // 即子串前綴和后綴的最長公共匹配字符數有l - 1個。 13 // next[i] = j++; 14 // } else { 15 // next[i] = j; 16 // j = 0; 17 // if (pattern[i] == pattern[j]) { 18 // j++; 19 // } 20 // } 21 // } 22 23 int j = 0; 24 next[0] = -1; 25 int p_len = pattern.length(); 26 int matched = 0; 27 while (++j <= p_len) { 28 int right = j - 1; 29 int mid = floor(right / 2); 30 int left = right % 2 == 0 ? mid - 1 : mid; 31 int curLeft = left; 32 int curRight = right; 33 while (curLeft >= 0) { 34 if (pattern[curLeft] == pattern[curRight]) { 35 matched++; 36 curLeft--; 37 curRight--; 38 } else { 39 matched = 0; 40 curLeft = --left; 41 curRight = right; 42 } 43 } 44 next[j] = matched; 45 matched = 0; 46 } 47 }
根據next數組求模式串在主串中的位置代碼如下：
int search(string source, string pattern, int next[]) { int i = 0; int j = 0; int p_len = pattern.length(); int s_len = source.length(); while (j < p_len && i < s_len) { if (j == -1 || source[i] == pattern[j]) { i++; j++; } else { j = next[j]; } } if (j < pattern.length()) return -1; else return i - pattern.length(); }
測試代碼如下：
int main() { string source = "ABCDABCEAAAABASABCDABCADABCDABCEAABCDABCEAAABASABCDABCAABLAKABCDABABCDABCEAAADSFDABCADABCDABCEAAABCDABCEAAABASABCDABCADABCDABCEAAABLAKABLAKK"; // string pattern = "abcaaabcab"; string pattern = "ABCDABCEAAABASABCDABCADABCDABCEAAABLAK"; int next[pattern.length()] = { NULL }; get_next(pattern, next); cout << "next數組: \t"; for (int i = 0; i < pattern.length(); i++) cout << next[i] << " "; cout << endl; int pos = search(source, pattern, next); if (-1 != pos) { cout << "匹配成功，模式串在主串中首次出現的位置是: 第" << pos + 1 << "位"; getchar(); return 0; } else { cout << "匹配失敗"; } getchar(); return 0; }
執行結果：
next數組: -1 0 0 0 0 1 2 3 0 1 1 1 2 1 0 1 2 3 4 5 6 7 1 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 匹配成功，模式串在主串中首次出現的位置是: 第97位
KMP算法優化
再回過頭去看模式串2的next數組的圖：
如果模式串和主串的匹配在j = 6(b)處失敗的話，根據j = next[6] = 1得知下一次匹配從j = 1處開始，j = 1處的字符和j = 6處的字符同為c，因此這次匹配必定會失敗。
同樣的，模式串和主串的匹配在j = 7(c)處或在j = 9(b)處失敗的話，根據next數組偏移后下一次匹配也必定會失敗。
考慮如果模式串是: aaaac，根據一般的KMP算法求出的next數組及匹配過程如下：
顯而易見，在第二次匹配失敗后，第三、四、五次匹配都是沒有意義的，j = next[3]、j = next[2]、j = next[1]、j = next[0]這四處的字符都是a，在j = 3(a)處匹配失敗時，根據模式串本身就應該可以得出結論：可以跳過j = 2(a)、j = 1(a)、j = 0(a)的匹配，直接從i = i + 1 、j = 0處開始匹配，所以優化過后的next數組應該是：
代碼實現
優化后的求next數組的代碼如下：
void get_next(string pattern, int next[]) { // ！！！！！！！！！！由網友(評論第一條)指出該算法存在問題，更新后的代碼在上方，新算法的優化代碼暫未實現，但是優化思路是正確的。 // int i = 0; // i用來記錄當前計算的next數組元素的下標， 同時也作為模式串本身被匹配到的位置的下標 // int j = 0; // j == -1 代表從在i的位置模式串無法匹配成功，從下一個位置開始匹配 // next[0] = -1; // next[0]固定為-1 // int p_len = pattern.length(); // while (++i < p_len) { // if (pattern[i] == pattern[j]) { // // j是用來記錄當前模式串匹配到的位置的下標， 這就意味著當j = l時， // // 則在pattern[j]這個字符前面已經有l - 1個成功匹配, // // 即子串前綴和后綴的最長公共匹配字符數有l - 1個。 // next[i] = j++; // // // 當根據next[i]偏移后的字符與偏移前的字符向同時 // // 那么這次的偏移是沒有意義的，因為匹配必定會失敗 // // 所以可以一直往前偏移，直到 // // 1): 偏移前的字符和偏移后的字符不相同。 // // 2): next[i] == -1 // while (next[i] != -1 && pattern[i] == pattern[next[i]]) { // next[i] = next[next[i]]; // } // } else { // next[i] = j; // j = 0; // if (pattern[i] == pattern[j]) { // j++; // } // } // } }
浙公網安備 33010602011771號