KMP 算法：找子串的位置

简介

字符串的算法中，有一个是做模式匹配，让你找子串的位置。

如果用暴力解法，那就是一个双重 for 循环，以主串的每个字符为开头，往后走，看是不是跟子串完全一致。这样的算法时间复杂度是 $O(n \times m)$。有没有更好的算法呢？

KMP（Knuth-Morris-Pratt） 是三个科学家的名字，他们发现，在暴力解法中有些情况没必要从头开始比对，由此提出了基于 match 数组（也称部分匹配表，记录了串 $a_0…a_k$ 的最大相同前后缀）的 “主指针不回退” 的时间复杂度为 $O(n + m)$ 的算法。

代码

主要思想是，主指针一直往前走不回退，让模式串的指针跳转到可以开始匹配的位置（由 next 数组得出），省去不必要的匹配，以此节省时间。由于主指针不回退，因此匹配的时间复杂度是 O(n)。

next 数组表示模式串跳转的位置，从这个位置的下一个字符开始与主串进行比较，构建 next 数组的时间复杂度是 O(m)。

这两部份加起来，时间复杂度是 O(n+m)。

KMP 算法的正确性可以用数学归纳法、形式化方法等来证明，也可以直观理解。

class Solution:
    def kmp(self, main_str: str, sub_str: str) -> int: 
        n,m = len(main_str), len(sub_str)
        if n < m:
            return -1
        if m == 0:  # 处理空模式串
            return 0
        next_arr = self.buildNext(sub_str)
        i, j = 0, 0 # 初始化
        while (i < n) and (j < m):
            if main_str[i] == sub_str[j]:
                # 往前走比对
                i += 1
                j += 1
            elif j > 0:
                # 跳转
                j = next_arr[j - 1] + 1
            else:
                # 跳转到 -1 了
                i += 1
        return i - m if m == j else -1

    def buildNext(self, sub_str: str) -> list: 
        m = len(sub_str)
        next_arr = [-1] * m
        for i in range(1, m):
            j = next_arr[i - 1] # 跟前一个的关系
            while (j >= 0) and (sub_str[i] != sub_str[j + 1]):
                # 不断回退
                j = next_arr[j]
            if sub_str[i] == sub_str[j + 1]:
                # 正好相等
                next_arr[i] = j + 1
            else:
                # 回退到重置状态
                next_arr[i] = -1
        return next_arr

    def strStr(self, haystack: str, needle: str) -> int:
        return self.kmp(haystack, needle)

对应题目：

• 28. 找出字符串中第一个匹配项的下标
• 459. 重复的子字符串：找到最长相同前后缀，剩下的东西，是不是有什么特点

Python 中使用字符串的find()方法：返回子串第一次出现的索引，如果未找到则返回-1。使用了 Boyer-Moore-Horspool 算法。

Golang 中使用字符串包的 strings.Index() 方法：返回子串第一次出现的索引，如果未找到则返回-1。使用了 Rabin-Karp 算法。

分析

next 数组构建分析之长度定义

事实上，next 数组的构建，看起来像极了动态规划（重叠子问题+最优子结构）：

• 状态的含义：dp[i]: 表示前 i 个字符的最大相同真前缀和真后缀的长度

  Tip

  我们还可以这样直接全部用索引来形式化定义，避免中途需要 长度-1=索引 的问题：$$ match[i] = \begin{cases} k, 满足 p_0 \ldots p_k = p_{i-k}\ldots p_{i} 的最大k (< i) \\ -1, 如果这样的 k 不存在 \end{cases}$$ 本文按一般的动态规划思想用长度定义是为便于理解。 后文也先用长度定义来推导，最后再介绍这种位置定义的推导，第2章的代码是用的位置定义。

• 状态转移方程：看跟 $dp[i - 1]$ 的关系，如果当前字符 s[i] 匹配上 s[dp[i - 1] - 1 + 1] 就能直接 + 1 （这里 - 1 是字符数组下标和字符串长度的问题， + 1 是下一个字符），否则只能接着回退，看跟 $dp[dp[i - 1]]$ 的关系

  $$ dp[i] = \begin{cases} dp[i - 1] + 1, & s[dp[i - 1] - 1 + 1] = s[i] \\ dp[dp[i - 1]] + 1, & s[dp[dp[i - 1]] - 1 + 1] = s[i] \\ … \end{cases} $$

  还可以画图理解,下方的四个带颜色的块都是相同的，大块套小块：

  

• 初始化：dp[0] = -1（从长度角度看这就是 KMP 算法的另一个精妙之处，从位置定义来看，这就是不存在那样的k时的特殊值）

• 遍历顺序：从左往右

• 举例推导：以 ABABC 为例

next 数组构建分析之位置定义

最后，我们看一下，如果按位置定义来推导，会如何之顺畅：

1. 定义（找位置）： $ dp[i] = \begin{cases} k, 满足 p_0 \ldots p_k = p_{i-k}\ldots p_{i} 的最大k (< i) \\ -1, 如果这样的 k 不存在 \end{cases}$
2. 转移方程：$ dp[i] = \begin{cases} dp[i - 1] + 1, & s[dp[i - 1] + 1] = s[i] \\ dp[dp[i - 1]] + 1, & s[dp[dp[i - 1]] + 1] = s[i] \\ …\end{cases}$
3. 初始化：dp[0] = -1 （按定义来）
4. 遍历顺序：从左往右
5. 举例推导：ABABC
   dp[0] = -1
   dp[1] = -1 –> dp[0] = -1 –> s[0] != s[1] -回退到-1了-> dp[1] = -1
   dp[2] = 0 –> dp[1] = -1 –> s[0] = s[2] –> dp[2] = 0
   dp[3] = 1 –> dp[2] = 0 –> s[1] = s[3] –> dp[3] = 1
   dp[4] = -1 –> dp[3] = 1 –> s[2] != s[4] -回退dp[1]=-1了-> dp[4] = -1

结果发现，这种按位置的形式化定义，还真畅快，这便是 next 数组的构建。

KMP 举例推导

主串 s：ABABACDA

模式串 p：ABABC

next 数组：-1, -1, 0, 1, -1

• i = 0, j = 0 –> s[0] = p[0]
• i = 1, j = 1 –> s[1] = p[1]
• i = 2, j = 2 –> s[2] = p[2]
• i = 3, j = 3 –> s[3] = p[3]
• i = 4, j = 4 –> s[4] != p[4] -j跳转=next[4-1]+1(下一个字符)=next[3]+1=2-> s[2] = s[2] = p[4]
• i = 5, j = 3 –> s[5] != p[3] -j=next[2]+1=1-> –> s[5] != p[1] -j=next[1]+1=0了-> j 归零，主指针往前走
• i = 6, j = 0 –> s[6] != p[0] -> j 归零，主指针往前走
• i = 7, j = 0 –> s[7] = p[0]
• i = 8, j = 1 –> s 越界推出
• 未匹配上 –》 m != j –> -1