## KMP算法 KMP算法是用來在字符串內匹配子字符串的算法。 ## 最大前綴后綴長度 假設有字符串`abbacdeabba`,則最大前綴后綴為`abba`，長度為4。 ## 算法流程 1. 先計算出匹配串的最大前綴后綴長度的數組`next[]`。 2. 通過next[]數組來加速字符串匹配過程。 ## 代碼實現 ### 計算最大前綴后綴長度的數組`next[]` ~~~ /** * 求一個字符數組的next數組（最大公共前綴后綴長度） * @param chars * @return */ private static int[] getNextArray(char[] chars) { if(chars.length == 1){ return new int[]{-1}; } int[] next = new int[chars.length]; // 初始化0位置為-1，1位置上為0 next[0] = -1; next[1] = 0; // next數組的位置 int i = 2; int cn = 0; while (i < chars.length){ // 當前字符等于i-1位置的字符，則next數組里值=cn+1 if (chars[i - 1] == chars[cn]) { next[i++] = ++cn; }else if(cn > 0) { // cn向前移動 cn = next[cn]; }else{ // cn=0了，則無法向前移動，則next里的值為0 next[i++] = 0; } } return next; } ~~~ ### 字符串匹配過程 ~~~ /** * kmp算法的字符串下標查找方法 * @param str 數據字符串 * @param sub 查找子字符串 * @return 包含則返回匹配的第一個字符下標，沒找到則返回-1 */ private static int indexOf(String str,String sub){ if (str == null || sub == null || str.length() < 1 || str.length() < sub.length()) { return -1; } char[] strArr = str.toCharArray(); char[] subArr = sub.toCharArray(); int[] next = getNextArray(subArr); int i1 = 0; int i2 = 0; while (i1 < strArr.length && i2 < subArr.length){ // 相等，都后移 if(strArr[i1] == subArr[i2]){ i1++; i2++; }else { // 不相等，且前綴數組為-1，說明前移到0下標了，沒法繼續前移了 if (next[i2] == -1) { // 沒法使用前綴了 i1++; } else { // 沒有移動到0下標，則前移至前綴記錄位置 i2 = next[i2];// 前移 } } } // i1 或者 i2 有一個越界了 return i2 == subArr.length ? i1 - i2 : -1; } ~~~ ### 測試 ~~~ public static void main(String[] args) { String str = "abbacdeabbad"; int[] next = getNextArray(str.toCharArray()); System.out.println(Arrays.toString(next)); System.out.println(indexOf(str,"abbad")); System.out.println(str.indexOf("abbad")); } ~~~ 輸出： ``` [-1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 3, 4] 7 7 ```