首页

# KMP 模板

学习自《程序员代码面试指南》，作者左程云

最经典的字符串匹配问题，力扣链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/submissions/

要对查找串建立 next 数组，也就是前后缀匹配数组

private int[] getNext(char[] m) {
    int n = m.length;
    if(n <= 1) return new int[]{-1};
    
    int[] next = new int[n];
    next[0] = -1; next[1] = 0;
    int pos = 2, cn = 0;
    while(pos < n) {
        if(m[pos-1] == m[cn]) next[pos++] = ++cn;
        else if(cn > 0) cn = next[cn];
        else next[pos++] = 0;
    }
    return next;
}

然后通过 next 数组进行快速匹配字符串

public int match(Sting s, String m) {
    int sn = s.length(), mn = m.length();
    if(sn < mn) return -1;
    
    char[] arrS = s.toCharArray(), arrM = m.toCharArray();
    int[] next = getNext(arrM);
    int i = 0, j = 0;
    while(i < sn && j < mn) {
        if(arrS[i] == arrM[j]) {
            i++;
            j++;
        } else if(next[j] == -1) i++;
        else j = next[j];
    }
    
    return j == mn ? i - j : -1;
}

# 其他写法

在此我们看一下力扣官方对于 kmp 的写法，这里需要提的是，上一个方法算的 next 数组的 next[i] 表示从 0~i-1 的前缀与后缀相同的长度，我们定义的 next 长度只有 n ，所以它其实不能得到从 0~n-1 的前缀与后缀相同的长度。其实方法选一个自己喜欢的就好了，我个人是比较喜欢上面的方法，因为先学的那个。

int[] next = new int[mn]; // 从 1 开始，next [0] 默认为 0
for (int i = 1, j = 0; i < mn; i++) {
    //m [i] 就是当前的字符，在上一个方法中，是当前字符的前一个字符
    while (j > 0 && m[i] != m[j]) j = next[j - 1];
    if (m[i] == m[j]) j++;
    next[i] = j;
}

# 扩展题

kmp 算法需要求出一个 next 数组，这个数组可以解决一些衍生问题：

力扣 214. 最短回文子串，难度【困难】：https://leetcode.cn/problems/shortest-palindrome/

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例1
输入：s = "aacecaaa"
输出："aaacecaaa"
示例2
输入：s = "abcd"
输出："dcbabcd"
该题的一种解法就需要用到 next 数组，因为这题本质就是找到 s 的最长前缀回文字符串，假设 s 可以表示为 【】> 【】表示回文串，> 表示不回文），那么将这个 s 反转一下就成了 <【】 ，将两个字符串拼接一下： 【】>*<【】 ，这样的字符串肯定回文，但不是最短的，我们只是借助这个字符串形成的 next 数组判断最长前缀回文字符串。
public String shortestPalindrome(String s) {
	StringBuilder sb = new StringBuilder();
    sb.append(s);
    sb.append("*"); // 如果 s 是 aa 这样的，不加 * 就是 aaaa，那么 next 的结果就是 4，需要加 * 使其为 aa*aa
	sb.append(new StringBuilder(s).reverse());
    
    int[] next = new int[sb.length()+1];
    next[0] = -1; next[1] = 0;
    int pos = 2, cn = 0;
    while(pos <= sb.length()) {
        if(sb.charAt(pos-1) == sb.charAt(cn)) next[pos++] = ++cn;
        else if(cn > 0) cn = next[cn]; 
    	else next[pos++] = 0;
    }
    
    return new StringBuilder(s.substring(next[sb.length()], s.length())).reverse() + s;
}