KMP算法详解(python实现)_python3 kmp

---

前言

KMP算法是一个高效的串匹配算法。由D.E.Knuth和V.R.Pratt提出，J.H.Morris也几乎同时独立发现了这个算法，因此它被称为KMP算法。这个算法确实比较复杂，不太容易理解。但与朴素的串匹配算法相比，KMP算法的效率有本质的提高。

---

朴素匹配算法

为了理解KMP算法的想法，首先需要了解朴素匹配算法的缺陷，因此我们先分析朴素匹配算法。

最简单的朴素匹配算法采用最直观可行的策略：

1. 从左到右逐个字符匹配；
2. 发现不匹配时，转去考虑目标串里的下一个位置是否与模式串匹配。

如下图所示是一个朴素匹配示例：

上面的长串是目标串，下面是模式串。状态(0)和(1)两个串的第一对字符不同，将模式串右移一位。状态(2)顺序比较，第一对字符相同，但第二对字符不同，将模式串再右移一位…
下面是朴素匹配算法的一个实现：

def naive_matching(t, p):
    m, n = len(p), len(t)
    i, j = 0, 0
    while i < m and j < n:  # i==m说明找到匹配
        if p[i] == t[j]:    # 字符相同，考虑下一对字符
            i, j = i+1, j+1
        else:               # 字符不同，考虑t中下一位置
            i, j = 0, j-i+1
    if i == m:              # 找到匹配，返回其开始下表
        return j-i
    return -1               # 无匹配，返回特殊值
1
2
3
4
5
6
7
8
9
10
11

注：本文中p为模式串，t为目标串。

朴素匹配算法非常简单，容易理解，但其效率极低。造成其低效的主要因素是执行中可能出现回溯：匹配中遇到一对字符不同时，模式串p将向右移一个字符的位置，随后的匹