ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何实现 KMP 字符串匹配算法？

如何实现 KMP 字符串匹配算法？

原创 Python 作者：mingtian66 时间：2024-11-11 12:05:20 0 删除 编辑

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在主字符串（文本）中查找一个模式字符串的位置。与朴素的字符串匹配算法相比，KMP 算法通过预处理模式字符串，避免了不必要的比较，从而提高了匹配效率，特别是在处理大文本时表现尤为出色。
KMP 算法的基本思想

KMP 算法主要包括两个部分：

    前缀函数（部分匹配表）的构建：预处理模式字符串，计算每个位置的最长相等前后缀长度，用于在匹配失败时决定模式字符串的移动位置。
    匹配过程：利用前缀函数在主字符串中进行高效匹配，避免回溯主字符串的指针。

实现步骤

    构建前缀函数（部分匹配表）：
        对于模式字符串的每个位置，计算其前缀和后缀的最长公共长度。
        该表用于在匹配失败时，指示模式字符串应向右移动的位数。

    进行字符串匹配：
        使用两个指针分别遍历主字符串和模式字符串。
        当字符匹配时，两个指针同时移动。
        当字符不匹配时，根据前缀函数调整模式字符串的指针位置，主字符串的指针不回溯。

Python 实现

以下是 KMP 算法的详细 Python 实现，包括前缀函数的构建和匹配过程：

def compute_lps(pattern):
    """
    计算模式字符串的最长前缀后缀数组（LPS数组）。
    LPS[i] 表示模式字符串中，子串 pattern[0:i] 的最长相等前后缀的长度。
    """
    lps = [0] * len(pattern)
    length = 0  # 前一个最长前后缀长度
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # 回溯到上一个可能的最长前后缀
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    """
    使用 KMP 算法在文本中搜索模式字符串。
    返回模式字符串在文本中出现的所有起始索引。
    """
    if not pattern:
        return []

    lps = compute_lps(pattern)
    result = []
    i = 0  # 主字符串的指针
    j = 0  # 模式字符串的指针

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1

            if j == len(pattern):
                # 找到一个匹配
                result.append(i - j)
                j = lps[j - 1]  # 继续查找下一个可能的匹配
        else:
            if j != 0:
                # 根据 LPS 数组调整模式字符串指针
                j = lps[j - 1]
            else:
                i += 1

    return result

使用示例

假设我们要在主字符串中查找模式字符串的位置：

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

# 调用 KMP 搜索函数
matches = kmp_search(text, pattern)

print("模式字符串在主字符串中的起始索引位置:", matches)

输出

模式字符串在主字符串中的起始索引位置: [10]

解释

在上述示例中：

    主字符串 text 为 "ABABDABACDABABCABAB"。
    模式字符串 pattern 为 "ABABCABAB"。
    KMP 算法在主字符串中找到模式字符串一次匹配，起始索引位置为 10。

详细说明

    计算 LPS 数组：

    以模式字符串 "ABABCABAB" 为例，计算其 LPS 数组：
    索引 i    字符    LPS[i]
    0    A    0
    1    B    0
    2    A    1
    3    B    2
    4    C    0
    5    A    1
    6    B    2
    7    A    3
    8    B    4

    LPS 数组为 [0, 0, 1, 2, 0, 1, 2, 3, 4]。

    匹配过程：
        开始时，主字符串指针 i = 0，模式字符串指针 j = 0。
        比较 text[i] 和 pattern[j]，如果匹配则同时移动指针。
        当 j 达到模式字符串的长度时，表示找到一个匹配，记录起始位置，并根据 LPS 数组调整 j。
        如果不匹配，根据 LPS 数组调整 j，主字符串指针 i 不回溯。

优势

    时间复杂度：O(n + m)，其中 n 是主字符串的长度，m 是模式字符串的长度。相比于朴素算法的 O(nm)，KMP 更加高效。
    无需回溯主字符串指针：通过预处理模式字符串，避免了不必要的字符比较，提高了匹配速度。

总结

KMP 算法通过构建 LPS 数组，实现了高效的字符串匹配，尤其适用于需要多次匹配的场景。掌握 KMP 算法不仅有助于理解字符串匹配的基本原理，还能在实际编程中应用于文本搜索、数据解析等多个领域。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048313/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 如何使用 Python 实现 Dijkstra 算法？
下一篇： throw 和 throws 的区别是什么？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603019

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593