代码随想录算法训练营第九天 | KMP

LeetCode 28. 实现 strStr()
LeetCode 459.重复的子字符串

KMP

当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

前缀表

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

最长公共前后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

前缀表要求的就是相同前后缀的长度。

找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

前缀表与next数组

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

时间复杂度分析

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

为了和力扣题目28.实现strStr保持一致，方便大家理解，以下文章统称haystack为文本串, needle为模式串。

都知道使用KMP算法，一定要构造next数组。

构造next数组

我们定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。 代码如下：

public void getNext(int[] next, String s) 

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

• 初始化
• 处理前后缀不相同的情况
• 处理前后缀相同的情况

1. 初始化：

定义两个指针 i 和 j ，j 指向前缀末尾位置，i 指向后缀末尾位置。

然后还要对next数组进行初始化赋值，如下：

int j = 0;
next[0] = 0;

这里使用前缀表（不减1）的形式初始化 j 。

next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是 j ）

所以初始化next[0] = j = 0。

2. 处理前后缀不相同的情况

因为j初始化为0，那么i就从1开始，进行s[i] 与 s[j]的比较。

所以遍历模式串s的循环下标i 要从 1开始，代码如下：

for (int i = 1; i < s.length(); i++) 

如果 s[i] 与 s[j]不相同，也就是遇到 前后缀末尾不相同 的情况，就要向前回退。

怎么回退呢？

next[j - 1]就是记录着j（包括j）之前的子串的相同前后缀的长度。

那么 s[i] 与 s[j] 不相同，就要找 j 前一个元素在next数组里的值（就是next[j - 1]）。

所以，处理前后缀不相同的情况代码如下：

while (j > 0 && s.charAt(j) != s.charAt(i)) {
    j = next[j-1];
}

3. 处理前后缀相同的情况

如果 s[i] 与 s[j] 相同，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。

if (s.charAt(j) == s.charAt(i)) {
    j++;
}
next[i] = j;

最后整体构建next数组的函数代码如下：

    public void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j-1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
    }

28.实现strStr 题目的整体代码如下：

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while(j > 0 && needle.charAt(j) != haystack.charAt(i)) {
                j = next[j - 1];
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
                j++;
            }
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    public void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j-1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
    }
}