KMP算法

概念

• KMP算法：一种字符串搜索算法。是第一个用于字符串匹配的线性时间算法。时间复杂度是O(m+n)。
• KMP算法（由Knuth、Morris、Pratt三人共同发表），其特点就是在一次字符串的遍历过程中就可以匹配出子串。
• KMP算法中的核心概念就是基于最大公共前后缀生成next数组，在匹配失败的时候避免了暴力算法中的回退所带来的高时间复杂度问题。

暴力匹配

在字符串匹配中，若我们使用暴力破解对主串和子串进行匹配，当匹配失败就回退到主串的下一个字符重新开始匹配。在最坏的情况下，此种方式的时间复杂度为O(m*n)。匹配流程下图所示。

KMP

在理解KMP算法的核心概念最大公共前后缀之前，我们需要先明白前缀和后缀的含义。

• 前缀：在字符串中除了最后一个字符外，所有以第一个字符开始的连续子串。

• 后缀：在字符串中除了第一个字符外，所有以最后一个字符结尾的连续子串。

由此可以得出最大公共前后缀：在字符串里所有前缀和后缀相等的子串中最长的那个(不能超过字符串长度)。

基于最大公共前后缀生成的next数组就是用于记录子串中不同位置的最大公共前后缀长度。也就是当匹配失败的时候，子串需要回退的位置。那么next数组是如何计算的呢？参考下图手算next数组流程。

1. next数组的第一位默认是-1，即当匹配失败的时候，子串往后移动一位继续匹配。
2. next数组的作用：若子串的第n个位置的与主串不匹配，那么需要将子串回退到next[n]的位置再次进行匹配。
3. 计算next[n]最大公共前后缀的子串范围是。

代码推导

next数组

推导过程

1. 若计算next[i+1]的值时，必然已经知道next[i]的值（类似动态规划）。
2. 假设next[i]=k，根据最大公共前后缀定义，那么此时必有：。
3. 若，则 。
4. 若, 若 ，根据最大公共前后缀定义，此时必有：，结合第二步的结果可得：。
5. 若$ C_{k-z} = C_{i} $，那么 $ next[i+1] = z + 1$。如果不相等则重复上述流程，直到最长公共前后缀的值为0就停止循环查找。

private static int[] getNext(char[] array) {
    final int length = array.length;
    int[] next = new int[length];
    int i = 0, j = -1;
    // -1表示从子串的下一位开始匹配
    next[i] = j;
    while (i < length - 1) {
        if (j == -1 || array[i] == array[j]) {
            next[++i] = ++j; // 相等就是在next[i]的基础上加一
        } else {
            j = next[j]; // 不相等就继续往前查找
        }
    }
}

字符串匹配

/**
 * 根据next数组进行匹配，返回匹配成功的第一个index，不匹配则返回-1
 */
public static int indexOf(char[] parent, char[] child) {
    int[] next = getNext(child);
    int p = parent.length;
    int c = child.length;
    int i = 0, j = 0;
    for (; i < p; i++) {
        // 子串循环完毕就退出
        if (j == c) {
            break;
        }
        // 因为next数组第一位必定是-1.额外处理下
        if (j == -1 || parent[i] == child[j]) {
            j++;
        } else {
           // 不相等就根据next数组回退指定位置
            j = next[j];
        }
    }
    return i == p - 1 ? -1 : i - j;
}

kmp是典型的空间换时间算法，其核心就是基于最大公共前后缀生成的next数组，从而避免了指针回溯问题。