Python实现KMP字符串匹配算法详解

KMP算法的核心机制与前后缀概念

KMP（Knuth-Morris-Pratt）算法主要用于在主串中精确查找模式串的位置。其核心优势在于当发生字符不匹配时，不需要像暴力匹配算法那样将主串指针回退，而是根据预先计算好的next数组，直接将模式串滑动到下一个合理位置。理解这一机制的前提是明确前缀与后缀的定义。

以模式串 abab 为例，假设当前考察到下标为 3 的字符（即第4位），此时需要截取长度小于当前位置的有效前缀集合与有效后缀集合进行比对：

• 有效前缀：a, ab, aba
• 有效后缀：b, ba, bab

算法的目标就是找出这两组集合中最长的相同部分。例如在位置 3 处，最长相等前后缀长度为 2（对应 ab），这直接决定了后续发生不匹配时的滑动偏移量。

第一步：构建模式串next数组

本步目的是为每个模式串位置预计算最长相等前后缀长度。入口为传入模式串 t 与待填充列表 next_arr。操作采用双指针策略：j 追踪当前模式串位置，k 记录已匹配的前缀长度。初始状态设 k = -1 且 next_arr[0] = -1。循环中若 k == -1 或 t[j] == t[k]，则 j 与 k 同步后移并存入 next_arr[j] = k；若不等，则执行 k = next_arr[k] 进行前缀回溯。可观察的完成状态为列表长度与模式串一致，且每个元素准确反映对应位置的最大前后缀重合度。

def GetNext(t, next_arr):
    j, k = 0, -1
    next_arr[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:  # 到达起点或当前字符与前缀对应字符匹配
            j += 1
            k += 1
            next_arr[j] = k          # 记录当前位置的最长相等前后缀长度
        else:                        # 字符不匹配，前缀长度回退
            k = next_arr[k]
    return next_arr

第二步：实现KMP主匹配逻辑

本步目的是完成主串与模式串的滑动比对。入口为主串 s 与模式串 t。初始化指针 i=0（主串）与 j=0（模式串）。循环条件为 i<len(s) 且 j<len(t)。当 j == -1 或 s[i] == t[j] 时双指针后移；一旦 s[i] != t[j]，程序保持 i 不动，直接赋值 j = next_arr[j] 实现模式串快速复位。完成判断标准为 j 越过模式串末尾，此时返回起始索引 i - len(t)，否则返回 -1。

def KMP(s, t):
    next_arr = [0] * len(t)
    GetNext(t, next_arr)
    print("计算得到的next数组:", next_arr)
    
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i += 1
            j += 1
        else:
            j = next_arr[j]  # 核心跳转：依据前缀表快速复位模式串指针
            
    if j >= len(t):
        return i - len(t)
    else:
        return -1

第三步：完整代码整合与运行验证

将上述模块合并为独立脚本后，可通过终端直接执行测试。以下为标准整合代码，包含数据定义与结果打印逻辑：

def GetNext(t, next_arr):
    j, k = 0, -1
    next_arr[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:
            j += 1
            k += 1
            next_arr[j] = k
        else:
            k = next_arr[k]
    return next_arr

def KMP(s, t):
    next_arr = [0] * len(t)
    GetNext(t, next_arr)
    print("计算得到的next数组:", next_arr)
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i += 1
            j += 1
        else:
            j = next_arr[j]
    if j >= len(t):
        return i - len(t)
    else:
        return -1

if __name__ == '__main__':
    target_text = 'asdfghjsssaaasdfaaaabababcdabd'
    pattern_str = 'ababaaaababaa'
    res_index = KMP(target_text, pattern_str)
    print("首次匹配起始下标:", res_index)

执行该脚本后，控制台将优先输出next数组的计算序列，随后打印出目标串中的匹配起始位置。实际运行结果如下图所示：

通过以上步骤，即可在Python中稳定复现KMP算法的匹配流程。实际开发中可根据具体业务场景调整字符串编码格式或补充边界异常处理。以上就是Python实现KMP算法的详细内容，更多关于Python字符串匹配技巧的资料请关注本站其它相关文章！