编辑“︁KMP算法”︁（章节）

= KMP算法 =

'''KMP算法'''（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在主文本字符串中查找模式字符串的出现位置。该算法通过利用模式字符串的部分匹配信息来避免不必要的字符比较，从而将时间复杂度从朴素算法的O(m*n)优化到O(m+n)，其中m是模式串的长度，n是主文本的长度。

== 算法原理 ==

KMP算法的核心思想是当模式串与主文本不匹配时，利用已知的匹配信息跳过一些不可能成功的比较。具体来说，它通过预处理模式串生成一个'''部分匹配表'''（Partial Match Table，简称PMT），也称为'''失败函数'''（Failure Function），来指导匹配失败时的跳转。

=== 部分匹配表（PMT） ===
部分匹配表记录了模式串中每个位置的最长'''公共前后缀'''长度。例如，对于模式串"ABABC"：

{| class="wikitable"
|+ 部分匹配表示例
! 索引 !! 子串 !! 最长公共前后缀长度
|-
| 0 || A || 0
|-
| 1 || AB || 0
|-
| 2 || ABA || 1 ("A")
|-
| 3 || ABAB || 2 ("AB")
|-
| 4 || ABABC || 0
|}

数学表示为：
<math>
\text{PMT}[i] = \max\{k \mid k < i \text{且} P[0..k-1] = P[i-k..i-1]\}
</math>

== 算法步骤 ==

1. '''预处理阶段'''：构建模式串的部分匹配表。
2. '''匹配阶段'''：使用部分匹配表在主文本中查找模式串。

=== 预处理实现 ===
以下是构建部分匹配表的Python实现：

<syntaxhighlight lang="python">
def build_pmt(pattern):
    pmt = [0] * len(pattern)
    length = 0  # 当前最长公共前后缀长度
    i = 1
    
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            pmt[i] = length
            i += 1
        else:
            if length != 0:
                length = pmt[length - 1]
            else:
                pmt[i] = 0
                i += 1
    return pmt
</syntaxhighlight>

=== 匹配实现 ===
使用PMT进行字符串匹配：

<syntaxhighlight lang="python">
def kmp_search(text, pattern):
    pmt = build_pmt(pattern)
    i = j = 0  # i遍历text，j遍历pattern
    
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                print(f"Pattern found at index {i - j}")
                j = pmt[j - 1]
        else:
            if j != 0:
                j = pmt[j - 1]
            else:
                i += 1
</syntaxhighlight>

== 示例分析 ==

'''输入'''：
* 主文本： "ABABDABACDABABCABAB"
* 模式串： "ABABCABAB"

'''输出'''：
Pattern found at index 10

'''匹配过程可视化'''：
<mermaid>
graph LR
    A[Start] --> B[Compare ABAB...]
    B -->|Match| C[Compare C vs D]
    C -->|Mismatch| D[Shift by PMT[4]=2]
    D --> E[Compare AB...]
    E -->|Match| F[Found at index 10]
</mermaid>

== 时间复杂度分析 ==

* 预处理阶段：O(m)
* 匹配阶段：O(n)
* 总时间复杂度：O(m+n)

对比朴素算法的O(m*n)，KMP在重复模式较多的场景下优势显著。

== 实际应用 ==

KMP算法广泛应用于：
1. 文本编辑器的查找功能
2. DNA序列匹配
3. 网络数据包的内容检测
4. 编译器的词法分析

== 变体与扩展 ==

* '''Boyer-Moore算法'''：另一种高效字符串匹配算法，适合字符集较大的情况
* '''Rabin-Karp算法'''：基于哈希的字符串匹配算法
* '''Aho-Corasick算法'''：多模式串匹配的扩展

== 练习建议 ==

1. 手动计算模式串"AAAAB"的部分匹配表
2. 实现KMP算法并测试不同输入
3. 比较KMP与朴素算法的性能差异
4. 尝试修改算法以查找所有匹配位置

[[Category:搜索算法]]
[[Category:字符串算法]]
[[Category:计算机科学]]

[[Category:数据结构与算法]]