失效函数 F[i] 表示当模式串和文本串匹配到第 i 个字符不匹配时，模式串应跳转至第 F[i] 个字符重新匹配。计算过程：F[0] = 0对于 P[0...i] (i > 0)，若 P[i] = P[F[i-1]], 则 F[i] = F[i-1] + 1若 P[i] ≠ P[F[i-1]], 则从 F[F[i-1]-1] 回溯，直到 P[F[F[i-1]-1]] = P[i], 则 F[i] = j + 1
KMP 失效函数计算教程
失效函数的定义
失效函数 F[i] 表示当模式串和文本串匹配到第 i 个字符时，如果模式串和文本串不匹配，则模式串应该跳转到哪个字符重新开始匹配。
失效函数的计算
失效函数的计算需要用到模式串的前缀和后缀。对于模式串 P，P[i] 表示模式串的第 i 个字符，P[0...i] 表示模式串从第 0 个字符到第 i 个字符构成的子串。
失效函数的计算分为两步：
-
计算长度为 1 的子串的失效函数
失效函数
F[0]始终为 0。 -
计算长度大于 1 的子串的失效函数
对于长度大于 1 的子串
P[0...i] (i > 0)，其失效函数F[i]的计算如下：- 若
P[i]与P[F[i - 1]]相同，则F[i] = F[i - 1] + 1。 - 若
P[i]与P[F[i - 1]]不同，则从F[F[i - 1] - 1]开始回溯，直到找到P[F[F[i - 1] - 1]]与P[i]相同为止，令此时回溯到的位置为j，则F[i] = j + 1。
- 若
举例说明
以模式串 P = "ababab" 为例：
-
F[0] = 0。 -
F[1] = 0，因为P[1] = "a"，P[F[0]] = P[0] = "a"。 -
F[2] = 1，因为P[2] = "b"，P[F[1]] = P[0] = "a"，所以从F[F[1] - 1] = F[0] = 0开始回溯，发现P[0] = "a"与P[2] = "b"不同，继续回溯，发现P[0] = "a"与P[1] = "a"相同，则F[2] = 1。
依次计算即可得到失效函数：F = [0, 0, 1, 2, 3, 4]。
失效函数的作用
失效函数可以在 KMP 算法中提高匹配速度。当模式串和文本串匹配到第 i 个字符时，如果字符不匹配，则直接跳转到模式串的第 F[i] 个字符处重新开始匹配。通过这种方式，可以避免从头开始重新匹配，从而提高算法效率。
