Skip to content

KMP.md

Latest commit

 

History

History
132 lines (90 loc) · 6.92 KB

KMP.md

File metadata and controls

132 lines (90 loc) · 6.92 KB

Knuth-Morris-Pratt 算法

Knuth-Morris-Pratt 算法，简称 KMP 算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表。

思路及算法

Knuth-Morris-Pratt 算法的核心为前缀函数，记作π(i)，其定义如下：

对于长度为 m 的字符串 s，其前缀函数 π(i)(0≤i<m) 表示 ss 的子串s[0:i] 的 最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那 么π(i)=0。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

我们举个例子说明：字符串 aabaaab 的前缀函数值依次为 0,1,0,1,2,2,3。

  • π(0)=0，因为 a 没有真前缀和真后缀，根据规定为 0（可以发现对于任意字符串 π(0)=0 必定成立）；

  • π(1)=1，因为 aa 最长的一对相等的真前后缀为 a，长度为 1；

  • π(2)=0，因为 aab 没有对应真前缀和真后缀，根据规定为 0；

  • π(3)=1，因为 aaba 最长的一对相等的真前后缀为 aa，长度为 1；

  • π(4)=2，因为 aabaa 最长的一对相等的真前后缀为 aa，长度为 2；

  • π(5)=2，因为 aabaaa 最长的一对相等的真前后缀为 aa，长度为 2；

  • π(6)=3，因为 aabaaab 最长的一对相等的真前后缀为aab，长度为 3。

有了前缀函数，我们就可以快速地计算出模式串在主串中的每一次出现。

如何求解前缀函数

长度为 m 的字符串 s 的所有前缀函数的求解算法的总时间复杂度是严格 O(m) 的， 且该求解算法是增量算法，即我们可以一边读入字符串，一边求解当前读入位的前缀函数。

为了叙述方便，我们接下来将说明几个前缀函数的性质：

  • π(i)≤π(i−1)+1

    • 依据π(i) 定义得：s[0:π(i)−1]=s[i−π(i)+1:i]
    • 将两区间的右端点同时左移，可得：s[0:π(i)−2]=s[i−π(i)+1:i−1]
    • 依据π(i−1) 定义得：π(i−1)≥π(i)−1，即 π(i)≤π(i−1)+1

  • 如果s[i]=s[π(i−1)]，那么 π(i)=π(i−1)+1

    • 依据 π(i−1) 定义得：s[0:π(i−1)−1]=s[i−π(i−1):i−1]
    • 因为 s[π(i−1)]=s[i]，可得 s[0:π(i−1)]=s[i−π(i−1):i]
    • 依据 π(i) 定义得：π(i)≥π(i−1)+1，结合第一个性质可得 π(i)=π(i−1)+1

这样我们可以依据这两个性质提出求解π(i) 的方案：找到最大的 j，满 足s[0:j−1]=s[i−j:i−1]，且 s[i]=s[j]。（这样就有 s[0:j]=s[i−j:i]， 即π(i)=j+1）

注意这里提出了两个要求：

  1. j 要求尽可能大，且满足 s[0:j−1]=s[i−j:i−1]；
  2. j 要求满足 s[i]=s[j]。

由π(i−1) 定义可知：s[0:π(i−1)−1]=s[i−π(i−1):i−1] (1)

那么 j=π(i−1) 符合第一个要求。如果s[i]=s[π(i−1)]，我们就可以确定π(i)。

否则如果s[i]≠s[π(i−1)]，那么π(i)≤π(i−1)，因为j=π(i)−1，所以j < π(i−1)， 于是可以取 (1) 式两子串的长度为 j的后缀，它们依然是相等的 ：s[π(i−1)−j:π(i−1)−1]=s[i−j:i−1]。

当 s[i]≠s[π(i−1)] 时，我们可以修改我们的方案为：找到最大的 j，满 足s[0:j−1]=s[π(i−1)−j:π(i−1)−1]，且s[i]=s[π(i−1)]。（这样就有 s[0:j]=s[π(i−1)−j:π(i−1)]，即 π(i)=π(i−1)+1）

注意这里提出了两个要求：

  1. j 要求尽可能大，且满足s[0:j−1]=s[π(i−1)−j:π(i−1)−1]；
  2. j 要求满足s[i]=s[j]。

由π(π(i−1)−1) 定义可知j=π(π(i−1)−1) 符合第一个要求。如果 s[i]=s[π(π(i−1)−1)]，我们就可以确定π(i)。

此时，我们可以发现 j 的取值总是被描述为π(π(π(…)−1)−1) 的结构（初始 为π(i−1)）。于是我们可以描述我们的算法：设定 π(i)=j+1，j 的初始值为 π(i−1)。我们只需要不断迭代 j（令 j 变为 π(j−1)）直到s[i]=s[j] 或j=0 即可，如果最终匹配成功（找到了 j 使得s[i]=s[j]），那么π(i)=j+1，否 则π(i)=0。

复杂度证明

时间复杂度部分，注意到 π(i)≤π(i−1)+1，即每次当前位的前缀函数至多比前一位增加一 ，每当我们迭代一次，当前位的前缀函数的最大值都会减少。可以发现前缀函数的总减少次 数不会超过总增加次数，而总增加次数不会超过 m 次，因此总减少次数也不会超过 m 次，即总迭代次数不会超过 m 次。

空间复杂度部分，我们只用到了长度为 m 的数组保存前缀函数，以及使用了常数的空间 保存了若干变量。

如何解决本题

记字符串 haystack 的长度为 n，字符串needle 的长度为 m。

我们记字符串 str=needle+#+haystack，即将字符串 needle 和 haystack 进行拼接 ，并用不存在于两串中的特殊字符 # 将两串隔开，然后我们对字符串 str 求前缀函数 。

因为特殊字符 # 的存在，字符串 str 中 haystack 部分的前缀函数所对应的真前缀 必定落在字符串 needle 部分，真后缀必定落在字符串 haystack 部分。当 haystack 部分的前缀函数值为 m 时，我们就找到了一次字符串needle 在字符串 haystack 中的出现（因为此时真前缀恰为字符串needle）。

实现时，我们可以进行一定的优化，包括：

  1. 我们无需显式地创建字符串 str。
    • 为了节约空间，我们只需要顺次遍历字符串 needle、特殊字符 # 和字符串 haystack 即可。
  2. 也无需显式地保存所有前缀函数的结果，而只需要保存字符串needle 部分的前缀函数 即可。
    • 特殊字符 # 的前缀函数必定为 0，且易知 π(i)≤m（真前缀不可能包含特殊字 符#）。
    • 这样我们计算π(i) 时，j=π(π(π(…)−1)−1) 的所有的取值中仅有π(i−1) 的下标 可能大于等于 m。我们只需要保存前一个位置的前缀函数，其它的 j 的取值将全 部为字符串 needle 部分的前缀函数。我们也无需特别处理特殊字符 #，只需要 注意处理字符串 haystack 的第一个位置对应的前缀函数时，直接设定 j 的初值 为 0 即可。

这样我们可以将代码实现分为两部分：

  1. 第一部分是求 needle 部分的前缀函数，我们需要保留这部分的前缀函数值。
  2. 第二部分是求 haystack 部分的前缀函数，我们无需保留这部分的前缀函数值，只需 要用一个变量记录上一个位置的前缀函数值即可。当某个位置的前缀函数值等于 m 时 ，说明我们就找到了一次字符串 needle 在字符串 haystack 中的出现（因为此时 真前缀恰为字符串 needle，真后缀为以当前位置为结束位置的字符串 haystack 的 子串），我们计算出起始位置，将其返回即可。