kmp算法失效函数怎么求教程

失效函数 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. 计算长度为 1 的子串的失效函数

   失效函数 F[0] 始终为 0。

   

   影像之匠PixPretty

   商业级AI人像后期软件，专注于人像精修，色彩调节及批量图片编辑，支持Windows、Mac多平台使用。适用于写真、婚纱、旅拍、外景等批量修图场景。

   299

   查看详情

2. 计算长度大于 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] 个字符处重新开始匹配。通过这种方式，可以避免从头开始重新匹配，从而提高算法效率。

以上就是kmp算法失效函数怎么求教程的详细内容，更多请关注php中文网其它相关文章！