子字符串查找（上）：從暴力算法到KMP

子字符串查找(串匹配)很常用，當你在文本編輯器中使用搜索功能定位某個單詞或者在瀏覽器中輸入一個關鍵字搜索網頁，你可能從未意識到此時你面臨的正是子字符串查找問題，你得到了想要的結果，而這背後起作用的就是某一個子字符串查找算法。

問題可描述為：

文本T = Life becomes a lot more fun when you know that it is meaningless

模式P = fun

將文本串的長度記作N,即N = |T|;模式串的長度記作M，即M = |P|.通常有N >> M >> 1

問題已經清楚了，那麼有哪些策略可以用來解決這個問題呢？

首先最容易想到的就是暴力解法：將文本串和模式串的首字符對齊，依次比對每一個字符，若在某一位置比對失敗，將模式串自左向右移動一個單位，重新開始新一輪的比較。

具體實現：定義兩個指針，指針i跟蹤文本，指針j跟蹤模式，將邏輯上的模式串自左向右移動轉化為：把指針i指向的位置作為與模式串匹配的起始位置,i的取值範圍為[0,N-M]。在每一個特定的i將其後（包含i本身）長度為j的子串依次與模式串的每個字符比對，當出現不同字符時，將j重置為0，i向後移動一個單位，不斷重複這一過程，直至i越界（匹配失敗）或者當匹配成功時返回i的位置。

代碼如下：

publicstaticint search(String txt, String pat) {

int N = txt.length();

int M = pat.length();

for (int i = 0; i <= N - M; i++) {

int j;

for (j = 0; j < M; j++) {

if (txt.charAt(i + j) != pat.charAt(j)) {

break;

}

if (j == M) return i;//匹配成功

}

}

return N;//匹配失敗

}

暴力算法的正確性毋庸置疑，它的效率怎麼樣呢？

最好情況：對於每一特定的i在起始位置就與模式串不匹配，在這種情況下只需N-M+1次比較，即O(N)；

最壞情況：對於某一特定的i,在與模式串比對過程中，前M-1項皆匹配成功，第M項比對失敗，也就是說文本串中的每個字符都與模式串中的每一個字符比對一次，在這種情況下需要進行（N-M+1）* M次比較，即O(N*M)；

對於一個算法我們通常考慮其最壞情況，因為它給出了算法運行時間的上界，即為我們提供了一個保證：該算法在任何情況下的運行時間都不會大於該上界。

O（N*M）顯然是不能接受的，我們想要的是即使在最壞情況下也能在線性時間內完成子字符串查找的算法。

稍加思考，不難發現，暴力解法每次只向右移動一個字符，這是制約該算法性能的主要原因，能不能突破這個瓶頸呢？答案是肯定的。

針對暴力解法的不足，KMP算法進行了兩處改進：

1.一次右移多個字符

2.避免已匹配的字符串重複比對

KMP算法是如何做到這兩點的呢？KMP提前構造了一張查詢表。美妙的是查詢表的構建與文本串無關，使得我們可以根據模式串提前構造查詢表，KMP也因此具有了預知功能，這是KMP能夠提高效率的關鍵。

為什麼next表的構建與文本串無關呢？如下圖所示，在P[j]之前模式串與文本串完全相等（長度記作partial_match_length），因此，我們可以只考慮模式串。再進一步，前綴是由P[j]決定的，只需對每一個j構建next表（查詢表），而j的取值範圍不過是[0,M)。

j為模式串的索引，j == partial_match_length（例：j=3時考慮的是模式串中的前3個字符P[0,3)）。以next[j] == 3為例,一次向右滑動partial_match_length - 3個位置，也就是說將P[next[j]]處的字符移動到P[j],即P[j] = P[next[j]],這一操作實現了一次右移多個字符。又因為相對於P[j]的前綴，其首部和尾部具有一定的相似性,已知P[0,next[j])與P[j-next[j],j)完全匹配，即可從P[j]處重新開始比對。

令最大自匹配的真前綴和真後綴的長度為t; KMP算法能夠快速滑過j-2t個字符，避免重複比對t個字符。

綜上，模式串與文本串在某一位置匹配失敗後，KMP算法能告訴我們應該將模式串中的哪個字符移動到比對失敗處，並且從失敗處重新開始比對。

既然next表決定了KMP算法的走向，那麼next表應該如何構建呢？表中的每一項又有什麼具體含義呢？

next[j]代表什麼？next[j]的值是模式串中長度為partial_match_length的子字符串真前綴與真後綴完全匹配的最大長度。模式串中partial_match_length為0的子串（首字符的前綴），首字符的前綴為空，令next[0]=-1;

j=6，即partial_match_length=6，對應的子字符串為：ababab所有真前綴為：a,ab,aba,abab,ababa；所有真後綴為：babab,abab,bab,ab,b.可得真前綴與真後綴完全匹配的最大長度為4(abab)，所以next[6]=4.

這裡使用了一個小技巧：在模式串的左端設置一個哨兵，索引為-1，字符是一個通配符，能夠匹配所有的字符。這樣做的好處有兩個：保持算法邏輯上的統一；使算法更加簡潔。

在計算next[j+1]時，當P[j]不等於P[next[j]]以及後續許多P[next of next of next of … next[j]]，最後收斂於1+next[0]，若next[0] == 0，P[next[0]] == P[0] != P[j]，需要單獨對這種情況進行處理，算法的邏輯和實現都更加複雜。

以計算next[j+1](j=6為例):

P[6] == c != P[next[6]] == a, 計算P[next[next[6]]] == P[2] == a != c，計算P[next[next[next[6]]]] == P[0] == a != c，接著計算P[next[next[next[next[6]]]]] == P[-1] == c推出next[7] = 1 + next[0],即next[7]=0;

觀察這個計算過程， P[0] == a != c如果不設置哨兵，這種情況該怎麼處理呢？（體會一下設置少哨兵的妙處）

知道了next表的含義，接下來就該從代碼的角度構建next表了：已知next[0,j],計算next[j+1],當P[j] == P[next[j]]，next[j+1] = next[j] + 1；當P[j] != P[next[j]]，依次比對P[j]與P[next[next[j]]]…最壞的情況收斂於P[j] == P [next[0]],此時next[j+1] = 1 + next[0];

next表的構建代碼如下：

publicstaticint buildNext(String pat) {

int M = pat.length();

int j = 0;

int[] next = newint[M];

next[0] = -1;

while (j < M -1) {

if (0 > next[j] || pat.charAt(j) ==pat.charAt(next[j])) {

next[++j] = ++next[j];

} else {

next[j] = next[next[j]];

}

}

return M;

}

KMP算法很聰明，那麼它是完美的嗎？至少現在我們的KMP算法還有改進的空間。看下面一種情況：

當P[j] != T[I + j]時,用P[next[j]]替換P[j]，觀察上圖可知多了三次不必要的比對，能不能避免這種情況呢？問題出在了哪裡呢？

用來替換P[j]的P[next[j]]和P[j]相等，匹配會繼續失敗。

對於匹配失敗處的字符，KMP能告訴我們它應該是什麼，如果它也能告訴我們不應該是什麼，那麼上面例子中的三次不必要的比對就可以避免。

改進後的KMP算法如下:

publicstaticint buildNextElevate(String pat) {

int M = pat.length();

int j = 0;

int[] next = newint[M];

next[0] = -1;

while (j < M -1) {

if (0 > next[j] || pat.charAt(j) ==pat.charAt(next[j])) {

j++; next[j]++;

next[j] = pat.charAt(j) !=pat.charAt(next[j]) ? next[j] : next[next[j]];//與前一版本的不同之處

} else {

next[j] = next[next[j]];

}

}

return M;

}

在最壞情況下，暴力算法確實很慢，但它就真的一無是處嗎？

首先，它能正確的解決問題，其次，它為我們提供了優化的思路和方向。對於很多問題，暴力解法往往不是最優的，但它卻是一個很好的開始。