Python实现字符串匹配的KMP算法

什么是KMP算法？

KMP算法是一种字符串匹配算法，可用于在一个字符串中查找另一个字符串出现的位置。它的核心思想是，当子串与主串不匹配时，可以利用已经得到的部分匹配结果，将子串移动到下一个可以匹配的位置，而不是从头开始逐个字符匹配。

KMP算法的步骤

KMP算法的实现主要有以下三个步骤：

1. 预处理模式串
   对于模式串的每一位，我们求出它的前缀和后缀的最长公共部分。得到一个next数组，其中next[i]表示前i个字符组成的子串中，最长的相等前后缀的长度。

2. 匹配过程
   对于主串和模式串，从左到右进行匹配，当匹配失败时，利用next数组将模式串向右移动一定的距离。

3. 返回匹配结果

KMP算法Python实现示例

我们以在一个字符串中查找另一个字符串出现的位置为例，实现KMP算法的Python代码如下：

def kmp_search(pattern, text):
    """
    KMP算法查找主串中是否存在模式串，返回模式串在主串中的起始位置，或-1表示不匹配
    """
    # 构造next数组
    next = kmp_next(pattern)
    i, j = 0, 0
    while i < len(text) and j < len(pattern):
        if j == -1 or text[i] == pattern[j]:
            i, j = i+1, j+1
        else:
            j = next[j]
    if j == len(pattern):
        return i - j
    else:
        return -1

def kmp_next(pattern):
    """
    构造next数组
    """
    next = [-1] * len(pattern)
    i, j = 0, -1
    while i < len(pattern) - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i, j = i+1, j+1
            next[i] = j
        else:
            j = next[j]
    return next

示例说明

下面我们用两个例子来说明如何使用KMP算法在字符串中查找另一个字符串。

例子1

在字符串“ABABCABCDABABCABDE”中查找模式串“ABABCABD”出现的位置。

text = "ABABCABCDABABCABDE"
pattern = "ABABCABD"

pos = kmp_search(pattern, text)
if pos == -1:
    print("未找到")
else:
    print(f"找到，在位置{pos}")

输出：

找到，在位置6

例子2

在字符串“bananas”中查找模式串“nas”出现的位置。

text = "bananas"
pattern = "nas"

pos = kmp_search(pattern, text)
if pos == -1:
    print("未找到")
else:
    print(f"找到，在位置{pos}")

输出：

找到，在位置4

总结

本篇文章介绍了KMP算法的实现步骤和Python代码，以及两个使用KMP算法的示例说明。