KMP字符串匹配算法详解与代码实现

发布时间：2024-10-25 09:31:01

Blog标题：KMP字符串匹配算法详解与代码实现 93

本内容由，集智官方收集发布，仅供参考学习，不代表集智官方赞同其观点或证实其内容的真实性，请勿用于商业用途。

KMP字符串匹配算法是一种高效的字符串搜索算法，主要用于处理文本数据中的模式匹配问题。该算法通过使用前缀表来减少重复的比较步骤，从而提高了字符串搜索的效率。KMP算法的核心思想是在模式串中查找一个子串，使得在原字符串中从这个子串开始的位置开始进行匹配时，不会导致任何重复的比较步骤。在KMP算法中，我们首先创建一个前缀表，用于存储模式串中每个字符的出现位置。然后，我们从第一个字符开始，逐个检查模式串中的每个字符是否出现在前缀表中。如果某个字符不在前缀表中，我们就跳过它，继续检查下一个字符。如果某个字符在前缀表中，我们就将前缀表的相应部分向右移动一位。这样，我们就可以在不增加比较次数的情况下，找到模式串在原字符串中的位置。 KMP算法的主要优点是它可以在O(n+m)的时间复杂度内完成字符串匹配，其中n是模式串的长度，m是原字符串的长度。相比于朴素的字符串匹配算法（如暴力匹配），KMP算法具有更高的效率。

KMP字符串匹配算法详解与代码实现。

在现代软件开发中，字符串匹配是一个常见且重要的问题。

无论是搜索引擎的关键词匹配，还是文本编辑器中的查找和替换功能，高效的字符串匹配算法都是不可或缺的。

KMP（Knuth-Morris-Pratt）算法是一种经典的字符串匹配算法，它通过部分匹配表（前缀表）来避免重复匹配，从而大大提高了匹配效率。

本文将详细讲解KMP算法的原理，并通过代码一步步展示其实现过程。

什么是KMP算法？。

KMP算法由Donald Knuth、Vaughan Pratt和James H. Morris在1977年提出，用于在一个文本字符串中高效地搜索一个模式字符串。

KMP算法的核心思想是利用已经匹配的部分信息，避免从头开始重新匹配，从而提高匹配效率。

KMP算法的核心概念。

KMP算法的核心在于构建一个“部分匹配表”（也称为“前缀表”或“失效函数”）。

这个表记录了模式字符串中每个位置之前的子串的最长公共前后缀长度。

具体来说，对于模式字符串P，定义π[i]为子串P[0...i]的最长公共前后缀的长度。

例如，对于模式字符串"ababab"，其部分匹配表如下：



P:    a b a b a b
π:    0 0 1 2 3 4

解释： - π[0] = 0：单个字符没有前缀和后缀。

- π[1] = 0：子串"ab"没有前缀和后缀。

- π[2] = 1：子串"aba"的最长公共前后缀是"a"。

- π[3] = 2：子串"abab"的最长公共前后缀是"ab"。

- π[4] = 3：子串"abab"的最长公共前后缀是"aba"。

- π[5] = 4：子串"ababab"的最长公共前后缀是"abab"。

KMP算法步骤。

1. #构建部分匹配表#：首先根据模式字符串P构建部分匹配表π。

2. #进行匹配#：使用部分匹配表来进行文本T和模式P的匹配。

构建部分匹配表。

部分匹配表的构建过程如下：


def compute_prefix_table(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0  # length of the previous longest prefix suffix
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

进行匹配。

有了部分匹配表后，我们可以利用它来进行文本T和模式P的匹配：


def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    pi = compute_prefix_table(pattern)
    j = 0  # index for pattern
    i = 0  # index for text
    matches = []
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            matches.append(i - j)
            j = pi[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = pi[j - 1]
            else:
                i += 1
    
    return matches

示例代码及解释。

假设我们有一个文本字符串T = "ababcabcabababd"和一个模式字符串P = "ababd"，我们希望找到所有模式在文本中出现的位置。

以下是完整的代码实现及解释：


# 构建部分匹配表
def compute_prefix_table(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0  # length of the previous longest prefix suffix
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

# KMP搜索算法
def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    pi = compute_prefix_table(pattern)
    j = 0  # index for pattern
    i = 0  # index for text
    matches = []
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            matches.append(i - j)
            j = pi[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = pi[j - 1]
            else:
                i += 1
    
    return matches

# 主程序
if __name__ == "__main__":
    text = "ababcabcabababd"
    pattern = "ababd"
    matches = kmp_search(text, pattern)
    print(f"Pattern '{pattern}' found at positions: {matches}")

#运行结果#：



Pattern 'ababd' found at positions: [8]

总结。

KMP算法通过构建部分匹配表，避免了重复匹配，从而大大提高了字符串匹配的效率。

在实际应用场景中，如搜索引擎、文本编辑器等，KMP算法都能发挥重要作用。

希望本文能帮助你理解KMP算法的原理及其实现过程，让你在实际项目中能够灵活应用这一高效的字符串匹配算法。

KMP字符串匹配算法详解与代码实现 - 集智数据集