【LeetCode分享】KMP算法

1. 题目描述 28. 实现 strStr()

实现 strStr()函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。

示例 1：
输入：haystack = "hello", needle = "ll"
输出：2

示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：
输入：haystack = "", needle = ""
输出：0

2. 思路1 暴力求解

暴力求解思路比较简单，即在模式串和主串进行匹配的过程中，如果发现某个字符不匹配，则模式串从头开始，主串的指针回退到上一次开始位置的下一个位置，直到主串遍历完毕，或者提前匹配成功。

遍历主串所用的时间复杂度是 $O(n)$ ，而每次从一个字符开始的时候，都需要依次和模式串的每个字符进行比较，故总体时间复杂度为 $O(n*m)$ ，但是通常 $m << n$ 所以该方法的时间复杂度其实也不是很高，因而效率依然还是不错。

代码如下

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    let needle_len = needle.length
    if (needle_len === 0) return 0
    let res = -1
    for (let i = 0; i < haystack.length; i++) {
        // 如果第一个字符匹配上，则判断接下来的几个字符是不是相同
        if (haystack[i] === needle[0]) {
            if (haystack.substring(i, i + needle_len) === needle) {
                res = i
                break
            }
        }
    }
    return res
}

3. 思路2 KMP算法求解

KMP算法相比于暴力求解方法的优点在于，暴力求解每次匹配失败都会使得主串的指针回溯，而KMP算法则不会使得主串指针回溯，我们来通过例子理解一下。

1.png

从头开始匹配，当匹配到 $[d, e]$ 的时候，发现该字符匹配不上，主串的指针则会回退到b，与模式串重新开始匹配，具体过程如下

2.png

3.png

4.png

5.png

我们可以看到，暴力匹配的方式需要这样老实巴交的执行，才能发现匹配不成功。但是在①的时候，即 $[d, e]$ 匹配不成功时，我们发现之前的都是匹配上的，且匹配上的部分有前缀和后缀均为 $ab$ 的子串，在KMP算法中，我们不需要回溯主串指针，直接将模式串从真前缀位置 $ab$ 移动到真后缀 $ab$ 位置，即一下可以跳过步骤②和③直接到达④进行后续匹配。

6.png

为什么可以这么做呢？

因为我们在发现当 $[d, e]$ 匹配不上的时候，我们希望模式串有一个字符能够替代 $e$ 使得匹配继续进行，这时候我们发现，如果前面有真前缀和真后缀配对的话，那么我们可以用真前缀替换真后缀，使得模式串向后移动，真前缀的下一个字符则可以替代真后缀的下一个字符，也就是当前没有匹配上的 $e$ 从而使得匹配继续进行。不过需要注意的是，如果我们每次都去寻找真前缀和真后缀的话，实际上是很慢的！

这时候我们又发现了一个规律，当出现匹配不上字符的时候，模式串和主串在这个字符之前是完全匹配上的，那么说明寻找真前缀和真后缀压根和主串没有啥关系，只需要找模式串即可。我们定义一个数组 $\Pi$ ，其中 $\Pi[i]$ 表示 $s[0:i]$ 最长真前缀的长度

以本例的模式串为例，我们来计算一下 $\Pi$ 数组的值

pi[0] = 0, a没有真前缀
pi[1] = 0, ab没有真前缀
pi[2] = 0, abc没有真前缀
pi[3] = 1, abca有真前缀a
pi[4] = 2, abcab有真前缀ab
pi[5] = 0, abcabe没有真前缀

不难发现，数组 $\Pi$ 有几个重要的性质：

$\Pi[i] \leq \Pi[i-1]+1$ ，即 $\Pi [i]$ 的下一位的数值最多比当前值递增1。
当 $s[0:j-1]=s[i-j-1:i-1]$ 及 $s[i]=s[j]$ 时，有 $\Pi[i] = \Pi[i-1]+1$ 。

那么我们在构造数组 $\Pi$ 的时候，只需要执行如下操作：

1. 定义一个数组，长度等于模式串的长度，且pi[0] = 0
2. 令i = 1,j = 0开始遍历，如果pattern[i] != pattern[j]则说明未匹配成功，
     我们需要将j指针回退到一个可以使得pattern[i] == pattern[j]的位置，根据性质2，
     令j = pi[j - 1]
     若j回退到0的位置，则表示未找到这样一个合适位置，pi[i] = 0，i从下一个字符开始
3. 如果pattern[i] == pattern[j]，说明匹配成功，根据性质2，pi[i] = j+1

具体构造数组 $\Pi$ 的代码如下

/**
 * 构建pi数组
 * @param {string} pattern 模式串
 */
const getPi = (pattern) => {
    let i = 1,
        j = 0,
        m = pattern.length
    const pi = new Array(m).fill(0)
    while (i < m) {
        // 未匹配成功，j进行回溯，若回溯到j=0则表示不存在这样的真前缀
        // 回溯取j=pi[j-1]一步步向前试探
        while (j > 0 && pattern[i] !== pattern[j]) {
            j = pi[j - 1]
        }
        // 如果匹配上，则 pi[i] = j+1, 且i和j后移
        if (pattern[i] === pattern[j]) {
            pi[i++] = ++j
            // 如果j为0，则表示没真前缀，此时pi[i] = j, i和j后移
        } else if (j === 0) {
            pi[i++] = j
        }
    }
    return pi
}

有了预定义的数组 $\Pi$ 我们就可以开始进行KMP算法了。

1. 让主串和模式串的指针i和j分别从下标0开始匹配
2. 如果主串和模式串出现了字符不匹配，那么j需要进行回退到一个合适位置
     即j = pi[j-1]，如果j=0了，说明i从该字符开始无法找到匹配子串，i++
3. 如果匹配上，则i和j都向后移动
4. 如果j的值等于模式串长度，则说明找到了，返回此时子串的起始位置
5. 其他情况为未找到，返回-1

代码如下

/**
 * KMP算法实现
 * @param {string} s 主串
 * @param {string} pattern 模式串
 */
const strStr = (s, pattern) => {
    const n = s.length,
        m = pattern.length
    if (m === 0) return 0 // c语言的结果
    const pi = getPi(pattern)
    // 执行Kmp匹配过程
    for (let i = 0, j = 0; i < n; i++) {
        // 出现了某个字符不匹配的情况，需要j进行回溯
        while (j > 0 && s[i] !== pattern[j]) {
            j = pi[j - 1]
        }
        // 匹配成功，此时j++，循环结束后i++
        if (s[i] === pattern[j]) {
            j++
        }
        if (j === m) {
            // 匹配成功
            return i - j + 1
        }
    }
    return -1
}

【LeetCode分享】KMP算法