kmp 算法用动态规划思想更容易理解

[zjsxwc]

kmp 算法的核心是计算 Next 数组，但是网上流传的实现代码比较晦涩，这里用动态规划来计算 Next 更加容易理解。

#### 预先定义

P[] 为长度为 n 的匹配字符串，index 从 0 开始

Next[] 为要计算的数组，Next[j] 表示长度为 j 的字符串"P[0]P[1]...P[j-1]"的前缀等于后缀的最长长度，比如对于字符串 P 为"abCdabCe"来说其 Next[7]为 3 因为 abC 的长度为 3， 边界值 Next[0] = 0, Next[1] = 0

动态规划状态函数为 f(int j, char x)，f(j,x)表示长度为 j+1 的字符串"P[0]P[1]...P[j-1]x"
的前缀等于后缀的最长长度，比如对于字符串 P 为"abCdabCe"来说其 f(6, 'C')为 3 因为 abC 的长度为 3，很直接的我们可以知道 Next[j] = f(j-1, P[j])


#### 状态转移方程的三个情况

f(j, x) =

1. 当 x 等于 P[Next[j]+1] 时，f(j, x) = Next[j] + 1

2. 当 x 不等于 P[Next[j]+1] ， 且 j 为 0 时， 这就是边界条件，此时 f(j, x) = 0

3. 当 x 不等于 P[Next[j]+1] ， 且 j 不为 0 时，f(j, x) = f(Next[j], x)

#### 额外的解释说明

上面条件 1 与 2 很好理解，这里需要对条件 3 稍作解释。

我们先定义一个字符串上的操作 K，
使 K(P) = Next[len(P)]，也就是对 P 取最长前缀后缀相同长度。

对于匹配字符串 P"eaabCaeae"来说 Next[8]=2 因为"ea"长度为 2，当我们需要计算 Next[9]也就是 f(8, e)时 由于字符 e 不等于字符 a，所以条件 1 不满足，而由于我们知道 Next[8]是代表字符串"ea"是长度为 8 的子字符串"eaabCaea"的最长相同前缀与后缀长度，这里为了方便说明，我们给这两个前缀后缀分别命名为 pre8 与 suf8，pre8 与 suf8 都是长度为 2 的字符串"ea"，   我们要计算 Next[9]也就是 f(8, e)也就是相当于求新后缀字符串 "${suf8}e"的 K， 这是因为最末字符 e 的存在，如果可求 K 大于 0 那么另一个字符 e 必然也存在于 suf8 中，而 K("${suf8}e") 等于 K("${pre8}e")  等于 f(len(pre8), e) 等于 f(Next[8], e)


参考 https://www.cnblogs.com/dusf/p/kmp.html

更详细点解释，

我们要计算 Next[9]也就是 f(8, e)也就是相当于求新后缀字符串 "${suf8}e"的 K， 这是因为最末字符 e 的存在，如果可求 K 大于 0 那么另一个字符 e 必然也存在于 P 字符串的前缀 pre8 中，而 pre8 等同于 suf8，所以另一个 e 也必然被包含于 suf8 之中，而 K("${suf8}e") 等于 K("${pre8}e")  等于 f(len(pre8), e) 等于 f(Next[8], e)

[iFlicker]

万物皆可 dp😂

[zjsxwc]

我们要计算 Next[9]也就是 f(8, e)也就是相当于求新后缀字符串 "${suf8}e"的 K， 这是因为最末字符 e 的存在，如果可求 K 大于 0 那么另一个字符 e 必然也存在于 suf8 中，而 K("${suf8}e") 等于 K("${pre8}e") 等于 f(len(pre8), e) 等于 f(Next[8], e)

[zjsxwc]

由于二楼这句里面有点含糊，所以我 append 了更详细点的解释。