字符串模式匹配查找

定义与基本思想

字符串模式匹配（String Matching）是指在主串中查找与模式串相同的子串位置。常见算法有朴素算法、KMP 算法等。

字符串模式匹配演示

此处可扩展为KMP等算法的匹配过程动画。

主串与模式串对齐
next数组跳转演示
匹配/失配过程

常见算法

朴素算法（Brute Force）

逐一对齐主串和模式串，依次比较字符
时间复杂度 $O(mn)$ ， $m$ 为主串长度， $n$ 为模式串长度

KMP 算法

利用部分匹配表（next 数组）避免重复比较
时间复杂度 $O(m+n)$

适用场景

文本编辑器查找、替换
DNA 序列分析
信息检索、数据挖掘

算法描述

朴素算法伪代码：

for i = 0 to m-n:
    for j = 0 to n-1:
        if S[i+j] != P[j]:
            break
    if j == n:
        return i // 匹配成功
return -1

KMP 算法伪代码（简化）：

构建next数组
i = 0, j = 0
while i < m:
    if S[i] == P[j]:
        i++, j++
        if j == n: return i-n // 匹配成功
    else if j > 0:
        j = next[j-1]
    else:
        i++
return -1

时间复杂度分析

朴素算法： $O(mn)$
KMP 算法： $O(m+n)$

练习题

练习 1

简述 KMP 算法的基本思想及其优点。

参考答案

解题思路：考查 KMP 的核心思想和优势。

详细步骤：

利用 next 数组避免重复比较
提高匹配效率，时间复杂度 $O(m+n)$

答案：KMP 用 next 数组跳过已知匹配前缀，效率高。

练习 2

朴素算法和 KMP 算法的时间复杂度分别是多少？

参考答案

解题思路：直接比较两种算法复杂度。

详细步骤：

朴素算法 $O(mn)$
KMP 算法 $O(m+n)$

答案：朴素 $O(mn)$ ，KMP $O(m+n)$ 。

考研真题

真题 1

【2022·408】KMP 算法如何避免主串指针回溯？

参考答案

解题思路：利用 next 数组跳转。

详细步骤：

匹配失败时，主串指针不回溯
模式串指针根据 next 数组跳转

答案：KMP 用 next 数组避免主串回溯。