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

2023-04-16 00:00:00 字符串 匹配 递归

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。它的名字是由三位作者（D.E.Knuth、J.H.Morris和V.R.Pratt）的名字首字母组成的。

KMP算法的实现中，需要预处理模式串P，算法首先计算出一个部分匹配表（Partial Match Table），然后用这个表在文本串S中查找模式串P的出现位置。

部分匹配表是模式串P的每个前缀子串中，最长的既是该前缀的真前缀（不包括本身），也是该前缀的真后缀（不包括本身）的长度。例如，对于模式串P="ababc"，它的部分匹配表如下：

P a b a b c
长度 0 0 1 2 0

假设现在要在文本串S="pidancode.com"中查找模式串P="皮蛋编程"的出现位置。首先需要预处理模式串P，计算出它的部分匹配表。计算部分匹配表的代码如下：

def compute_partial_match_table(pattern):
    """
    计算部分匹配表
    """
    n = len(pattern)
    partial_match_table = [0] * n
    i, j = 1, 0
    while i < n:
        if pattern[i] == pattern[j]:
            j += 1
            partial_match_table[i] = j
            i += 1
        elif j > 0:
            j = partial_match_table[j-1]
        else:
            i += 1
    return partial_match_table

经过计算，得到模式串P的部分匹配表为：

P 皮 蛋 编 程
长度 0 0 0 0

这是因为模式串P中并不存在某个前缀既是真前缀又是真后缀。

然后就可以用这个部分匹配表，在文本串S中查找模式串P的出现位置。查找的代码如下：

def kmp_search(text, pattern):
    """
    在text中查找pattern的出现位置
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    partial_match_table = compute_partial_match_table(pattern)
    i, j = 0, 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return i - j
        elif j > 0:
            j = partial_match_table[j-1]
        else:
            i += 1
    return -1

对于本例，经过上述计算，可以得到模式串P的部分匹配表为：

P 皮 蛋 编 程
长度 0 0 0 0

在文本串S="pidancode.com"中查找模式串P="皮蛋编程"的出现位置，可以用以下代码实现：

text = "pidancode.com"
pattern = "皮蛋编程"
index = kmp_search(text, pattern)
print(index)  # 输出：-1

由于模式串P不在文本串S中，因此返回-1。

完整代码如下：

def compute_partial_match_table(pattern):
    """
    计算部分匹配表
    """
    n = len(pattern)
    partial_match_table = [0] * n
    i, j = 1, 0
    while i < n:
        if pattern[i] == pattern[j]:
            j += 1
            partial_match_table[i] = j
            i += 1
        elif j > 0:
            j = partial_match_table[j-1]
        else:
            i += 1
    return partial_match_table


def kmp_search(text, pattern):
    """
    在text中查找pattern的出现位置
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    partial_match_table = compute_partial_match_table(pattern)
    i, j = 0, 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return i - j
        elif j > 0:
            j = partial_match_table[j-1]
        else:
            i += 1
    return -1


text = "pidancode.com"
pattern = "皮蛋编程"
index = kmp_search(text, pattern)
print(index)  # 输出：-1

相关文章