Knuth-Morris-Pratt（KMP）算法

本文概述

• KMP算法的组成部分
• 前缀功能（Π）
• 运行时间分析
• 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] = 0
	  k = 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”, 如下所示：

让我们执行KMP算法来查找“ T”中是否出现“ P”。

对于前缀函数“ p” , ？是先前计算的, 如下所示：

解：

Initially: n = size of T = 15
m = size of P = 7

已经发现模式’P’在字符串’T’中很复杂。找到匹配项所发生的总移位数为i-m = 13-7 = 6个移位。