字符串匹配之KMP算法

ByWhat'sUs

字符串匹配之KMP算法

假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况，从而避免 BF 算法这种暴力匹配，提高算法性能。下面我们来看下这个规律如何找到。

参考下面个主串和模式串的匹配，当模式串移动到当前位置，比对到最后一个字符 D 时，发现与主串不匹配，如果按照 BF 算法，就是把模式串往后移一位，再逐个比较，这样做固然可以，但是效率很差。

MNK ABCDAB ABCDABCDABDCBE
    ABCDABD

一个基本事实是，当 D 与主串不匹配时，我们已知前面的主串序列是 ABCDA，如果把模式串往后移一位肯定和主串不匹配，我们可不可以直接把模式串移到下一个可能和 A 匹配的主串位置？

实际上，KMP 算法正是基于这一理念，设法利用这个已知信息，不把模式串移到已经比较过的位置，继续把它向后移，这样综合下来就极大提高了搜索匹配效率。

这里，我们要解释几个概念：

• 后缀子串：以某个字符串最后一个字符为尾字符的子串（不包含字符串自身），比如上面的 ababa，后缀子串为 baba、aba、ba、a；
• 前缀子串：以某个字符串第一个字符为首字符的子串（不包含字符串自身），还是以 ababa 为例，前缀子串为 a、aba、abab；
• 最长可匹配后缀子串：后缀子串与前缀子串最长可匹配子串，也可叫做共有子串，以 ababa 为例，自然是 aba 了，长度为 3；
• 最长可匹配前缀子串：与上面定义相对，即前缀子串与后缀子串最长可匹配子串。最长可匹配前缀子串和最长可匹配后缀子串肯定是一样的。

假设坏字符所在位置是 j，最长可匹配后缀子串长度为 k，则模式串需要后移的位数为 j-k。每当我们遇到坏字符，就将模式串后移 j-k 位，直到模式串与对应主串字符完全匹配；如果移到最后还是不匹配，则返回 -1。这就是 KMP 算法的核心思想。

package main

import "fmt"

// 生成 next 数组
func generateNext(p string) []int {
    m := len(p)
    next := make([]int, m, m)
    next[0] = -1
    next[1] = 0
    i, j := 0, 1 // 前缀子串、后缀子串起始位置
    // 因为是通过最长可匹配前缀子串计算，所以 j 的值最大不会超过 m-1
    for j < m - 1 {
        if i == -1 || p[i] == p[j] {
            i++
            j++
            // 设置当前最长可匹配前缀子串结尾字符下标
            next[j] = i
        } else {
            // 如果 p[i] != p[j]，回到上一个最长可匹配前缀子串结尾字符下标
            i = next[i]
        }
    }
    return next
}

// KMP 算法实现函数
func kmpSearch(s, p string) int {
    n := len(s)  // 主串长度
    m := len(p)  // 模式串长度
    next := generateNext(p) // 生成 next 数组
    i, j := 0, 0
    for i < n && j < m {
        // 如果主串字符和模式串字符不相等，
        // 更新模式串坏字符下标位置为好前缀最长可匹配前缀子串尾字符下标
        // 然后从这个位置重新开始与主串匹配
        // 相当于前面提到的把模式串向后移动 j - k 位
        if j == -1 || s[i] == p[j] {
            i++
            j++
        } else {
            j = next[j]
        }
    }
    if j == m {
       // 完全匹配，返回下标位置
        return i - j
    } else {
        return -1
    }
}

// 基于 KMP 算法实现查找字符串子串函数
func strStrV2(haystack, needle string) int {
    // 子串长度=0
    if len(needle) == 0 {
        return 0
    }
    //主串长度=0，或者主串长度小于子串长度
    if len(haystack) == 0 || len(haystack) < len(needle) {
        return -1
    }
    // 子串长度=1时单独判断
    if len(needle) == 1 {
        i := 0
        for ; i < len(haystack); i++ {
            if haystack[i] == needle[0] {
                return i
            }
        }
        return -1
    }

    // 其他情况走 KMP 算法
    return kmpSearch(haystack, needle)
}

func main() {
    s := "Hello, nice to meet you!"
    p := "to"
    pos := strStrV2(s, p)
    fmt.Printf("Find \"%s\" at %d in \"%s\"\n", p, pos, s)
}

性能分析

KMP 算法比 BF 算法实现起来要复杂的多，不过带来的好处是执行效率的提升，综合 KMP 算法实现函数和 next 数组生成函数，它的时间复杂度是 O(n+m)，其中 n 是主串长度，m 是子串长度，m 和 n 的值越大，性能比 BF 算法更好，考虑到对于较长的主串，m 相对于 n 而言一般可以忽略，所以可以把 KMP 算法的时间复杂度近似看作 O(n)。

这个性能还是相当不错的，因此，KMP 算法被广泛用于字符串查找和匹配场景。