只要你學過數據結構與算法分析，相信你對KMP算法應該都不陌生吧？如果你沒聽過，不要緊，今天我們就來聊一聊這個算法。建議最好拿一張草稿紙，然後邊看邊理解，這樣更有助於你對它的理解，更能理解它背後的精髓所在，相信你在理解完該算法之後，一定會大喊一聲：妙啊！
KMP算法的誕生
KMP算法是三位大牛：Knuth、Morris和Pratt同時發現的，於是取了他們名字的首字母然後組合起來，就成了該算法的命名。
KMP算法要解決的問題就是查找一個字符串str2是否在另一個字符串str1出現過，也即str1是否包含str2這個子串，舉個例子，可以看到下圖，str1中包含有str2這個子串(aab)。
暴力解
如果想要解決這個問題，我們很容易想到的一個算法是直接暴力遍歷解，從左到右一個個匹配。
如果這個過程中有某個字符不匹配，之後我們只需要比較i指針指向的字符和j指針指向的字符是否一致。如果一致就都向後移動，如果不一致，如圖，i和j指針指向的字符不相等。
str2右移動一位，然後繼續以上操作.
直到遍歷結束，最後匹配成功，可以返回str1包含str2.
這種暴力的算法簡單粗暴，可以解決該問題，其時間複雜度為O(M*N)，M為str1的長度，N為str2的長度。KMP是對暴力解的一個優化，時間複雜度能做到O(M+N)，它的核心精髓是利用了以前的比較信息，然後推斷此次比較。說起來有點抽象，繼續舉個例子。
KMP算法
str1和str2剛開始按照從左到右遍歷的順序依次比較，發現到下標為10的時候，b不等於x，那麼此時該怎麼做？
如果按照暴力的方法，是要將str2整個串往右移動一位，然後再次從左到右依次比較。
我們想一下，我們有沒有必要將str2向右移動一位，然後再從左到右依次比較呢？如果有必要的話，那它的前提條件必定是下圖中紅色圈起來的兩個範圍全部匹配上！但是如果我們事先已經知道如果str2右移一位，然後紅色圈起來的範圍是不可能匹配成功的，我們就不需要讓str2右移一位，而讓str2右移若干位。這就是KMP的精髓！
那麼我們到底怎麼樣才能知道str2到底向右移動幾位呢？又是怎麼知道str2右移一位是不可能匹配成功的呢？我們還是首先回到第一輪的匹配中。我們已經說了，str2能夠右移一位的前提是要下圖中綠色兩塊的字符要全部匹配上，我們才右移動一位，不能再傻傻地無腦向右移動一位了。
那麼在第一次的比較中，我們發現下標0~9範圍內，str1和str2是全部匹配的，換句話說，str2中的綠色兩塊要完全匹配，我們才右移動！那我們怎麼知道str2中的兩塊綠色是否完全匹配呢？這就又引出了一個KMP中的核心內容——前綴與後綴的最大匹配長度（也就是next數組）。
前綴與後綴的最大匹配長度
舉個簡單的例子，一個字符串abcabck，那麼對於k字符來講，它前面的字符串所構成的前綴與後綴最大匹配長度為3，如下圖所示。
那麼這玩意有什麼用呢？回到剛才的例子
我們看一下str2相對於下標為10的字符前面的字符串所構成的前綴與後綴最大匹配長度是多少，按照上面的方法算一下，是5。
這就意味著，如果像剛才那樣右移一位的話，那str2相對於下標為10的前綴與後綴最大匹配長度應該為9，但是現在只有5，所以右移一位肯定不能和str1匹配。
那麼應該移動多少位呢？沒錯，就是5位。然後接著去匹配。
至此，關於KMP的大體思路已經講解完畢，接下來的關鍵就是如何求出一個字符串中對於所有位置的前綴與後綴最大匹配長度。也就是我們常說的next數組。
如何求next數組
我們人為規定了next[0]=-1和next[1]=0，即0位置的前綴與後綴最大匹配長度是-1，而1位置的前綴與後綴最大匹配長度是0.現在我們假設要求i位置的前綴與後綴最大匹配長度，而現在又知道i-1位置的前綴與後綴最大匹配長度為7，那麼，如果j位置的字符和i-1位置的字符相等的話，就可以得到i位置的前綴與後綴最大匹配長度為7+1=8.
如果i-1位置的字符和j位置的字符不相等的話，而我們又知道j位置的前綴與後綴最大匹配長度為3，那麼我們就去看看k位置的字符是否和i-1位置的字符相等，如果相等，則i位置的前綴與後綴最大匹配長度為3+1=4。如果不等，則再繼續以上操作，直到跳到0位置處，如果此時0位置還依然和i-1不等的話，那麼i位置的前綴與後綴最大匹配長度為0。
以上這一段看著可能有點複雜，但是實際上很好理解，大家用紙和筆來畫一下就清楚了！
下面是求next數組的代碼
<code> \tpublic static int getIndexOf(String s, String m) {
\t\tif (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
\t\t\treturn -1;
\t\t}
\t\tchar[] str1 = s.toCharArray();
\t\tchar[] str2 = m.toCharArray();
\t\tint i1 = 0;
\t\tint i2 = 0;
\t\tint[] next = getNextArray(str2); // O (M)
\t\t// O(N)
\t\twhile (i1 < str1.length && i2 < str2.length) {
\t\t\tif (str1[i1] == str2[i2]) {
\t\t\t\ti1++;
\t\t\t\ti2++;
\t\t\t} else if (next[i2] == -1) { // str2中比對的位置已經無法往前跳了
\t\t\t\ti1++;
\t\t\t} else {
\t\t\t\ti2 = next[i2];
\t\t\t}
\t\t}
\t\t// i1 越界 或者 i2越界了
\t\treturn i2 == str2.length ? i1 - i2 : -1;
\t}
/<code>利用next數組進行字符串匹配行為
按照以上的思路，我們就可以利用next數組去執行KMP算法了，最終我們是要得到str2在str1全匹配的str1的下標位置，以下圖為例，最終KMP算法是要返回8，因為str2是在str1的下標為8的位置處匹配上的，如果str2沒有被包含在str1中，那麼返回-1.
下面是利用next數組進行KMP算法的代碼
<code>public static int[] getNextArray(char[] ms) {
\t\tif (ms.length == 1) {
\t\t\treturn new int[] { -1 };
\t\t}
\t\tint[] next = new int[ms.length];
\t\tnext[0] = -1;
\t\tnext[1] = 0;
\t\tint i = 2; // next數組的位置
\t\tint cn = 0;
\t\twhile (i < next.length) {
\t\t\tif (ms[i - 1] == ms[cn]) {
\t\t\t\tnext[i++] = ++cn;
\t\t\t} else if (cn > 0) { // 當前跳到cn位置的字符，和i-1位置的字符配不上
\t\t\t\tcn = next[cn];
\t\t\t} else {
\t\t\t\tnext[i++] = 0;
\t\t\t}
\t\t}
\t\treturn next;
\t}/<code>
閱讀更多 IT界的泥石流 的文章
