博客

python实现kmp算法的实例代码

  • Post category:Python

KMP算法是一种字符串匹配算法，它的核心思想是利用已知信息避免无效的比较，从而提高匹配效率。在Python中，可以使用以下代码实现KMP算法。

KMP算法原理

KMP算法的核心思想是利用已知信息避免无效的比较，从而提高匹配效率。具体过程如下：

  1. 预处理模式串，得到next数组。next数组表示在模式串中，每个字符前面的子串中，最长的相等前缀和后缀的长度。
  2. 在文本串中匹配模式串。从文本串的第一个字符开始，依次比较文本串和模式串的每个字符，如果匹配成功，则继续比较下一个字符，否则根据next数组移动模式串的指针，直到匹配成功或者文本串结束。

Python实现KMP算法

预处理模式串

在Python中，可以使用以下代码预处理模式串，得到next数组。

def get_next(pattern):
    n = len(pattern)
    next = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    return next

在文本串中匹配模式串

在Python中，可以使用以下代码在文本串中匹配模式串。

def kmp(text, pattern):
    m, n = len(text), len(pattern)
    if n == 0:
        return 0
    next = get_next(pattern)
    j = 0
    for i in range(m):
        while j > 0 and text[i] != pattern[j]:
            j = next[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == n:
            return i - n + 1
    return -1

其中，text表示文本串，pattern表示模式串。执行上述代码后，会返回模式串在文本串中的起始位置，如果没有匹配成功，则返回-1。

示例说明

示例1

假设需要在一个字符串中查找另一个字符串的位置。可以使用上述代码实现KMP算法。具体代码如下：

text = 'hello, world!'
pattern = 'world'
pos = kmp(text, pattern)
print("模式串在文本串中的起始位置：", pos)

输出结果如下：

模式串在文本串中的起始位置： 7

示例2

假设需要在一个列表中查找另一个列表的位置。可以使用上述代码实现KMP算法。具体代码如下：

text = [1, 2, 3, 4, 5]
pattern = [3, 4]
pos = kmp(text, pattern)
print("模式串在文本串中的起始位置：", pos)

输出结果如下：

模式串在文本串中的起始位置： 2

总结

KMP算法是一种高效的字符串匹配算法，可以在O(m+n)的时间复杂度内完成匹配。在Python中，可以使用以上代码实现KMP算法，适用于字符串和列表等数据类型。

Tags: ,