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

什么是KMP算法

KMP算法是一种字符串匹配算法，其核心思想是利用已知信息尽量减少匹配的时间。
通常来说，我们在匹配字符串时，常用的方法是从头开始，逐个字符进行比较，直到匹配成功或者匹配失败为止。但是这种方法的效率并不高，尤其是在长串匹配的情况下，就会出现时间复杂度很高的问题。
KMP算法通过建立一个next数组，存储在匹配过程中已经匹配过的信息，从而避免了重复匹配的情况，使算法的效率得以提升。

KMP算法步骤

KMP算法的实现主要包括如下几个步骤：

1. 计算next数组：next数组中存储着在匹配字符串过程中已经匹配过的信息，用于在匹配失败时尽量减少匹配次数。
   具体计算方法是：在模式串中，以每个字符为尾的字符串中，最长的既是该字符串的前缀又是该字符串的后缀的字符串的长度。
   例如，模式串为“ababaca”，对应的next数组为[-1,0,0,1,2,0,1]。
   其中，next[0]=-1，next[1]=0，next[2]=0，以此类推。

2. 进行匹配：从主串的第一个字符开始，依次和模式串中的字符进行匹配。
   当匹配失败时，根据next数组的值，选择滑动到模式串中的哪一个位置继续匹配。
   当匹配成功时，返回主串中该子串的位置。

KMP算法实现示例

下面分别展示KMP算法的计算next数组和匹配主串的实现。

计算next数组

def get_next(p: str) -> list[int]:
    """
    计算next数组
    """
    m = len(p)
    next = [-1] * m
    k, j = -1, 0
    while j < m - 1:
        if k == -1 or p[k] == p[j]:
            k, j = k + 1, j + 1
            next[j] = k
        else:
            k = next[k]
    return next

以上代码中，函数get_next接受一个字符串p作为参数，返回p的next数组。
next数组初始化为-1，-1表示从模式串的开头开始匹配。
变量k和j分别指向模式串中的字符和next数组中的值，初始值为-1和0。
当p[k] == p[j]时，next[j+1]的值为k+1，表示下一次匹配时，主串的下一个字符和模式串的第k+1个字符进行比较。
否则，next[k]的值表示模式串向右移动的幅度。

匹配主串

def kmp_search(s: str, p: str) -> int:
    """
    KMP算法匹配主串
    """
    n, m = len(s), len(p)
    next = get_next(p)
    i, j = 0, 0
    while i < n and j < m:
        if j == -1 or s[i] == p[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j == m:
        return i - m
    return -1

以上代码中，函数kmp_search接受两个参数，s表示主串，p表示模式串，返回模式串在主串中的位置。
首先获取模式串的next数组，然后用变量i和j分别指向主串和模式串中的字符，初始值为0。
当匹配成功时，i和j分别递增，并继续匹配下一个字符。
当匹配失败时，更新j的值为next[j]。若next[j]=-1，则说明需要将模式串向右移动一位，即j+1。
当j = m时，说明匹配成功，返回主串中该子串的位置。

示例

代码如下：

s = "BBC ABCDAB ABCDABCDABDE"
p= "ABCDABD"
print(kmp_search(s,p)) # 输出15

以上代码中，主串s为BBC ABCDAB ABCDABCDABDE，模式串p为ABCDABD。
运行程序后，将返回模式串在主串中的位置，即15。