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”计算Π:

Knuth-Morris-Pratt算法

解:

Initially: m = length [p] = 7
	  Π [1] = 0
	  k = 0
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法

迭代6次后, 前缀函数计算完成:

Knuth-Morris-Pratt算法

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”, 如下所示:

Knuth-Morris-Pratt算法

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

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

Knuth-Morris-Pratt算法

解:

Initially: n = size of T = 15
m = size of P = 7
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法
Knuth-Morris-Pratt算法

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

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?