字符串匹配算法之 KMP 极简动画教程

一个会写诗的程序员

发布于 2021-04-23 11:08:43

5610

发布于 2021-04-23 11:08:43

文章被收录于专栏：一个会写诗的程序员的博客

实现 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

提示：

0 <= haystack.length, needle.length <= 5 * 104 haystack 和 needle 仅由小写英文字符组成

本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等，本文将讲解 KMP （Knuth-Morris-Pratt ）算法。

朴素暴力破解法

简单的循环判断即可。这里用一个 flagArray ，记录 needle 每个字符是否在 haystack 中。

代码

class Solution {
fun strStr(s: String, x: String): Int {
    if (x.isEmpty())
        return 0

    val sArray = s.toCharArray()
    val xArray = x.toCharArray()
    val width = x.length

    for (i in 0..(s.length - 1)) {

        if (i + width > s.length) {
            break
        }

        // 针对每一个 i， 遍历 x
        val flagArray = BooleanArray(width, { false })

        // 注意: 这地方的区间 [i, i + width - 1]
        (i..(i + width - 1)).forEachIndexed { index, k ->
            if (sArray[k] == xArray[index]) {
                flagArray[index] = true
            }
        }

        if (flagAllTrue(flagArray)) {
            return i
        }
    }

    return -1
}

fun flagAllTrue(flagArray: BooleanArray): Boolean {
    var flag = true
    flagArray.forEach {
        flag = flag && it
    }
    return flag
}
}

时间复杂度: O (m * n) 空间复杂度: O (m)

KMP 算法

KMP 算法的核心思想是在遍历模式串的过程中，把模式串的对称前后缀（等缀）部分记录下来，下一轮比对模式串的时候，直接把上一次已经比对的前缀（=后缀）部分跳过，直接来到 next（j）。

动画图示：

当下标为 i=5, j=5 的时候，发现 s[i]!=x[j], 接下来，要开始回溯。

首先，检查之前已经匹配成功的部分：aabaa（此时，要看next（4）= 2 ），判断是否存在相同的「前缀」和「后缀」;

if 存在( 这里是 aa )，则跳转到「前缀」的下一个位置( aabaaf )继续往下匹配。

前一个字符的前缀表的数值是2，所有把下标移动到下标2的位置继续比配。可以再反复看一下上面的动画。

定义:滑动步长 π(i) 函数如下： s[0..i] 前后等缀最大长度。

e.g. 模式串：x = aabaaf

π (0) = a = 0 π (1) = aa = 1 π (2) = aab = 0 π (3) = a ab a = 1 π (4) = aabaa = 2

说明一下：比如说，当模式串x 跟 s 的第 0..4 个字符均相等，那么如果第 5 个字符不相等，下一轮比对就可以直接从 aabaa 中的 baa 处开始比对了。因为，前面的aabaa跟后面的aabaa, 在上一轮比对的过程中已经匹配过，是相等的。)

π (5) = aabaaf = 0

这个 π(i) 函数也叫前缀表（prefix table）。前缀表有什么作用呢？前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

实现 π(i) 函数之后，按照上面动画演示的算法步骤实现源代码即可。

如果输入的模式串为 aabaaf，对应的 next 为 0 1 0 1 2 0，（其实这就是前缀表的数值了）。

那么用这样的next数组也可以用来做匹配。实现代码如下：

class Solution {
    fun strStr(s: String, x: String): Int {
        val m = x.length
        val n = s.length

        if (x.isEmpty()) {
            return 0
        }

        var j = 0
        // 模式串的最大等缀长度表
        val next = getNext(x)
        // 遍历 s[n]
        (0..n - 1).forEach {
            val i = it

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

            if (s[i] == x[j]) {
                j++
            }

            if (j == m) {
                return i - m + 1
            }


        }

        return -1

    }


    fun getNext(s: String): IntArray {
        val next = IntArray(s.length)
        var j = 0
        next[0] = j
        for (i in 1 until s.length) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1]
            }
            if (s[i] == s[j]) {
                j++
            }
            next[i] = j
        }
        return next
    }
}