Knuth-Morris-Pratt（KMP）算法 Knuth-Morris-Pratt算法|算法设计与

本文概述

KMP算法的组成部分
前缀功能（Π）
运行时间分析
KMP赛事
运行时间分析

【Knuth-Morris-Pratt（KMP）算法】Knuth-Morris和Pratt介绍了用于字符串匹配问题的线性时间算法。通过避免与先前与要匹配的模式“ p”的某个元素进行比较所涉及的“ S”元素进行比较, 可以实现O（n）的匹配时间。即, 永远不会发生字符串“ S”的回溯
KMP算法的组成部分 1.前缀功能（Π）：模式的前缀功能Π封装了有关模式如何与自身偏移匹配的知识。该信息可用于避免模式“ p”的无用移位。换句话说, 这可以避免回溯字符串“ S”。
2. KMP Matcher：使用字符串“ S”, 模式“ p”和前缀函数“Π”作为输入, 在“ S”中查找“ p”的出现并返回“ p”的移位次数, 之后出现的次数为找到了。
前缀功能（Π）以下伪代码计算前缀函数Π：

COMPUTE- PREFIX- FUNCTION (P) 1. m ←length [P]//'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π

运行时间分析在上述用于计算前缀函数的伪代码中, 从步骤4到步骤10的for循环运行’ m’ 次。步骤1至步骤3需要固定的时间。因此, 计算前缀函数的运行时间为O（m）。
示例：为以下模式“ p”计算Π：

文章图片
解：

Initially: m = length [p] = 7Π [1] = 0k = 0

文章图片

文章图片
迭代6次后, 前缀函数计算完成：

文章图片
KMP赛事 KMP匹配器以模式“ p”（字符串“ S”和前缀函数“Π”作为输入）在S中找到p的匹配项。下面的伪代码计算KMP算法的匹配组件：

KMP-MATCHER (T, P) 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0// numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q]// next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1// next character matches 10. If q = m// is all of p matched? 11. then print "Pattern occurs with shift" i - m 12. q ← Π [q]// look for the next match

运行时间分析从第5步开始的for循环运行’ n’ 次, 即与字符串’ S’ 的长度一样长。由于步骤1到步骤4需要固定的时间, 因此循环的运行时间主要由该时间决定。因此, 匹配函数的运行时间为O（n）。
示例：给定字符串“ T”和模式“ P”, 如下所示：