部分匹配表
KMP的关键是部分匹配表。理解KMP的主要障碍是没有完全掌握部分匹配表中的值到底意味着什么。试着用最简单的话来解释它们。
这是“abababca”模式的部分匹配表：
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
现在，为了谈论其含义，我们需要了解正确的前缀和正确的后缀。
正确的前缀：
字符串中的所有字符，其中一个或多个字符被截断。
“S”，“Sn”，“Sna”和“Snap”都是“Snape”的正确前缀。
截取的范围是从字符串的第一个字符到倒数第二个字符。
正确的后缀：
字符串中的所有字符，一个或多个字符在开头处截断。
“agrid”，“grid”，“rid”，“id”和“d”都是“Hagrid”的正确后缀。
截取的范围是从字符串的第二个字符到倒数第一个字符。
考虑到这一点，我现在可以给出部分匹配表中值的一句话含义：
（子）模式中与同一（子）模式中的正确后缀匹配的最长正确前缀的长度。
现在来分析“abababca”这个模式串：
对“a”分析，只有一个字符串，没有前缀和后缀，故值为0。
对“ab”分析，有一个正确的前缀（“a”）和一个正确的后缀（“b”），前缀和后缀不匹配，故值为0。
对“aba”分析，有两个正确的前缀（“a”和“ab”）和两个正确的后缀（“a”和“ba”）。正确的前缀“ab”与两个正确的后缀中的任何一个都不匹配。但是，正确的前缀“a”与正确的后缀“a”匹配。因此，在这种情况下，匹配正确后缀的最长正确前缀的长度是1。
对四个字符（“abab”）分析，有三个正确的前缀（“a”，“ab”和“aba”）和三个正确的后缀（“b”，“ab”和“bab”）。“ab”在两者中，并且是两个字符长，因此值为2。
对“ababa”分析，有四个正确的前缀（“a”，“ab”，“aba”和“abab”）和四个正确的后缀（“a”，“ba”，“aba”和“baba”）。现在，有两个匹配：“a”和“aba”都是正确的前缀和正确的后缀。由于“aba”比“a”长，所以它获胜，因此值为3。
对“abababc”分析。即使没有列举所有正确的前缀和后缀，显然也不会有任何匹配; 所有后缀都以字母“c”结尾，并且没有前缀与之匹配，因此值为0。
对“abababca”分析，由于它们都以“a”开头和结尾，我们知道它的值至少为1.但是，它就是它的结束点; 在长度为2或更高时，所有后缀都包含ac，而只有最长的前缀（“abababc”）包含“c”。这个七个字符的前缀与七个字符的后缀（“bababca”）不匹配，因此值为1。
如何使用部分匹配表
当我们找到部分匹配时，我们可以使用部分匹配表中的值来跳过（而不是重做不必要的旧比较）。该公式的工作方式如下：
如果找到长度为partial_match_length的部分匹配table[partial_match_length] > 1，我们可以跳过前面的partial_match_length - table[partial_match_length - 1]字符。
假设我们将“abababca”模式与“bacbababaabcbab”相匹配。这里是我们的部分匹配表，以便于参考：
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
我们第一次获得部分匹配是在这里：
bacbababaabcbab
|
abababca
这是partial_match_length为1. table[partial_match_length - 1]（或table[0]）的值为0，因此我们不会先跳过任何一个。我们得到的下一个部分匹配是：
bacbababaabcbab
|||||
abababca
这是partial_match_length为5. table[partial_match_length - 1]（或table[4]）的值为3.这意味着我们可以跳过前面partial_match_length - table[partial_match_length - 1]（或5 - table[4]或5 - 3或2）字符：
// x denotes a skip
bacbababaabcbab
xx|||
abababca
这是partial_match_length 3. table[partial_match_length - 1]（或table[2]）的值是1.这意味着我们可以跳过前面partial_match_length - table[partial_match_length - 1]（或3 - table[2]或3 - 1或2）字符：
// x denotes a skip
bacbababaabcbab
xx|
abababca
代码实现
def makeNext(pattern):
"""
求出模式串的最大前后缀长度数组
:param pattern: 模式串
:return:
"""
# 最大前后缀长度
k = 0
# 模版字符串长度
m = len(pattern)
next = [0] * (m-1)
# 模版字符串的第一个字符的最大前后缀长度为0
next.append(0)
# 从第二个字符开始，依次计算每一个字符对应的next值
for q in range(1, m):
# 求出P[0]···P[q]的最大的相同的前后缀长度k
while k > 0 and pattern[q] != pattern[k]:
k = next[k-1]
# 如果相等，那么最大相同前后缀长度加1
if pattern[q] == pattern[k]:
k = k + 1
next[q] = k
return next
def kmp(target, pattern):
"""
在目标串里查找模式串，成功查找后返回目标串中模式串出现位置的第一个下标
:param target: 目标串
:param pattern: 模式串
:return:
"""
# 目标串下标，不回溯
q = 0
# 目标串的长度
n = len(target)
# 模式串的长度
m = len(pattern)
# 求取模式串的匹配串数组
next = makeNext(pattern)
for i in range(1, n):
while q > 0 and pattern[q] != target[i]:
q = next[q-1]
# 模式串中的字符与目标串的字符相等，q向后移一位
if pattern[q] == target[i]:
q = q + 1
#
if q == m:
return i - m + 1
if __name__ == '__main__':
t = 'ACBDCBADAABCDABCA'
p = 'ABCDABC'
print(t)
print(p)
# next = makeNext(p)
result = kmp(t, p)
print(result)
网友评论