## 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 ```