Python中如何实现KMP字符串匹配算法

2023-04-17 00:00:00 算法 字符串 匹配

KMP算法全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的经典算法。它利用已知信息来避免无用的比较操作，从而提高算法的效率。Python中实现KMP算法可以分为以下几个步骤：

  1. 计算模式串的前缀函数值，即每个位置的最长匹配前缀子串长度。这个过程可以使用动态规划算法实现，时间复杂度为O(m)，m为模式串的长度。

  2. 在文本串中匹配模式串。开始匹配时，模式串的第一个字符与文本串的相同位置进行比较。如果匹配成功，则比较模式串的下一个字符和文本串的下一个字符。如果匹配失败，则利用前缀函数值跳过一部分比较，将模式串向右移动一段距离。具体来说，如果前k个字符匹配成功，第k+1个字符匹配失败，那么根据前缀函数值，可以将模式串移动到第k个字符对应的位置，从而避免重复比较。

下面是Python中的KMP算法实现，其中用到了列表的切片操作和字符串的索引操作。代码中以字符串“pidancode.com”和“皮蛋编程”为范例进行匹配。

def kmp_match(text, pattern):
    # 计算前缀函数值
    prefix = [0] * len(pattern)
    i, j = 0, 1
    while j < len(pattern):
        if pattern[i] == pattern[j]:
            prefix[j] = i + 1
            i += 1
            j += 1
        elif i > 0:
            i = prefix[i-1]
        else:
            j += 1

    # 在文本串中匹配模式串
    i, j = 0, 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j > 0:
            j = prefix[j-1]
        else:
            i += 1

    if j == len(pattern):
        return i - j
    else:
        return -1

text = "pidancode.com is a coding website."
pattern = "pidancode.com"
match_pos = kmp_match(text, pattern)
print("在文本串中匹配模式串：")
print("文本串：", text)
print("模式串：", pattern)
print("匹配位置：", match_pos)

text = "Hello, 皮蛋编程！"
pattern = "皮蛋编程"
match_pos = kmp_match(text, pattern)
print("在文本串中匹配模式串：")
print("文本串：", text)
print("模式串：", pattern)
print("匹配位置：", match_pos)

输出结果如下：

在文本串中匹配模式串：
文本串： pidancode.com is a coding website.
模式串： pidancode.com
匹配位置： 0

在文本串中匹配模式串：
文本串： Hello, 皮蛋编程！
模式串： 皮蛋编程
匹配位置： 7

相关文章