KMP模式匹配算法 (KMP Algorithm) 教案

1. 算法基础理论资料

算法定义与背景

KMP算法（Knuth-Morris-Pratt算法）是由Donald Knuth、Vaughan Pratt和James H. Morris三人于1977年联合发表的一种改进的字符串匹配算法。该算法通过预处理模式串，构建部分匹配表（也称为失效函数或next数组），在匹配失败时利用已匹配的信息，避免主串指针的回溯，从而提高匹配效率。

KMP算法是字符串匹配领域的经典算法之一，解决了朴素字符串匹配算法在最坏情况下时间复杂度为O(m*n)的问题。

问题定义

在主串（文本串）中查找模式串（pattern）的所有出现位置，其中主串长度为n，模式串长度为m。

数学基础

基于字符串理论、数组数据结构和模式匹配的数学概念。

2. 算法详细描述

算法思想

KMP算法的核心思想是当匹配失败时，利用已经匹配的部分信息，计算模式串应向右滑动的距离，避免主串指针的回溯。通过预处理模式串构建next数组，记录模式串中每个位置的最长相等前后缀长度。

算法步骤

构建next数组

初始化next[0] = 0；
设置两个指针i=1（后缀末尾）和j=0（前缀末尾）；
遍历模式串：
- 如果pattern[i] == pattern[j]，则next[i] = j + 1，i和j都加1；
- 如果pattern[i] != pattern[j]且j > 0，则j = next[j-1]；
- 如果pattern[i] != pattern[j]且j = 0，则next[i] = 0，i加1。

字符串匹配过程

设置主串指针i=0，模式串指针j=0；
当i < n且j < m时：
- 如果text[i] == pattern[j]，则i和j都加1；
- 如果j == m，说明找到匹配，记录位置i-j，然后j = next[j-1]继续查找；
- 如果text[i] != pattern[j]且j > 0，则j = next[j-1]；
- 如果text[i] != pattern[j]且j = 0，则i加1。

伪代码

算法 BuildNext(pattern)
输入：模式串pattern，长度为m
输出：next数组

next[0] = 0
j = 0
for i = 1 to m-1 do
    while j > 0 and pattern[i] != pattern[j] do
        j = next[j-1]
    if pattern[i] == pattern[j] then
        j = j + 1
    next[i] = j
return next

算法 KMP(text, pattern)
输入：主串text，长度为n；模式串pattern，长度为m
输出：所有匹配位置

next = BuildNext(pattern)
i = 0
j = 0
matches = 空列表
while i < n do
    if text[i] == pattern[j] then
        i = i + 1
        j = j + 1
    if j == m then
        将(i - j)加入matches
        j = next[j-1]
    else if i < n and text[i] != pattern[j] then
        if j != 0 then
            j = next[j-1]
        else
            i = i + 1
return matches

3. 算法实现

Python实现

def build_next(pattern):
    """
    构建KMP算法的next数组（部分匹配表）
    """
    m = len(pattern)
    next_array = [0] * m
    j = 0
    
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = next_array[j - 1]
        
        if pattern[i] == pattern[j]:
            j += 1
        
        next_array[i] = j
    
    return next_array

def kmp_search(text, pattern):
    """
    使用KMP算法在文本中搜索模式串
    """
    if not pattern:
        return []
    
    n, m = len(text), len(pattern)
    next_array = build_next(pattern)
    
    i = j = 0
    matches = []
    
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        
        if j == m:
            matches.append(i - j)
            j = next_array[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = next_array[j - 1]
            else:
                i += 1
    
    return matches

# 示例使用
def kmp_example():
    text = "ABABDABACDABABCABCABCABCABC"
    pattern = "ABABCABCABCABC"
    
    positions = kmp_search(text, pattern)
    print(f"Pattern found at positions: {positions}")
    
    # 验证结果
    for pos in positions:
        print(f"Match at position {pos}: {text[pos:pos+len(pattern)]}")

Java实现

import java.util.*;

public class KMPAlgorithm {
    
    /**
     * 构建KMP算法的next数组（部分匹配表）
     */
    public static int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        int j = 0;
        
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }
    
    /**
     * 使用KMP算法在文本中搜索模式串
     */
    public static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        
        if (pattern.isEmpty()) {
            return matches;
        }
        
        int n = text.length();
        int m = pattern.length();
        int[] next = buildNext(pattern);
        
        int i = 0, j = 0;
        
        while (i < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.add(i - j);
                j = next[j - 1];
            } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) {
                    j = next[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    // 示例使用
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABCABCABCABC";
        String pattern = "ABABCABCABCABC";
        
        List<Integer> positions = kmpSearch(text, pattern);
        System.out.println("Pattern found at positions: " + positions);
        
        // 验证结果
        for (int pos : positions) {
            System.out.println("Match at position " + pos + ": " + 
                             text.substring(pos, pos + pattern.length()));
        }
    }
}

4. 复杂度分析

时间复杂度

构建next数组：O(m)
字符串匹配过程：O(n)
总体时间复杂度：O(m + n)

空间复杂度

next数组：O(m)
总体空间复杂度：O(m)

数学证明

构建next数组的时间复杂度可以通过摊还分析证明为O(m)，因为j指针最多增加m次，减少的次数也不会超过增加的次数。匹配过程主串指针i只增加不减少，最多移动n次，模式串指针j可以增加也可以减少，但总体上也是线性时间复杂度。

5. 示例与案例

简单示例

主串："ABABDABACDABABCABCABCABCABC" 模式串："ABABCABCABCABC"

构建next数组过程和匹配过程的详细演示。

复杂案例

处理大量重复模式的文本
在基因序列中查找特定模式
在日志文件中搜索特定模式

边界条件

空主串或空模式串
模式串长度大于主串
模式串与主串完全相同
模式串在主串中无匹配

6. 算法可视化

可以通过动画演示next数组的构建过程，以及匹配过程中指针的移动和跳转。

7. 优缺点分析

优势

时间复杂度稳定，最坏情况下也是O(m+n)
避免了主串指针的回溯，适合处理流式数据
对于具有大量重复模式的字符串匹配效率很高

局限性

算法实现相对复杂，理解难度较大
需要额外的空间存储next数组
对于简单匹配场景，可能不如朴素算法直观

与其他算法的比较

相比于朴素字符串匹配算法的O(m*n)时间复杂度，KMP算法的O(m+n)具有显著优势；相比于Boyer-Moore算法，KMP算法更容易理解和实现。

8. 应用场景

实际应用

文本编辑器中的查找功能
生物信息学中的基因序列匹配
网络入侵检测系统中的模式匹配
数据压缩算法中的字典匹配

9. 练习与作业

理论题

证明KMP算法的时间复杂度为O(m+n)。
分析next数组的数学含义。

编程题

实现KMP算法，处理各种边界条件。
扩展KMP算法以支持通配符匹配。
比较KMP算法与其他字符串匹配算法的性能。

项目作业

设计一个文本搜索工具，使用KMP算法实现高效的多模式匹配功能。

FilesExpand file tree

kmp.md

Latest commit

History