字符串模式匹配查找

定义与基本思想

字符串模式匹配（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

KMP 算法的 next 数组推导

next 数组是 KMP 的核心：当模式串 $P[0..j]$ 在 $P[j]$ 处失配时， $j$ 应该回退到 next[j] 的位置。next[j] 等于 P[0..j-1] 的最长相等前后缀长度。

求 next 数组的步骤

next[0] = -1（第一个字符失配，主串指针后移）
递推求 next[j]：令 k = next[j-1]，若 P[j-1] == P[k]，则 next[j] = k+1；否则 k = next[k] 继续回退

示例：模式串 “abaabc”

j	0	1	2	3	4	5
P[j]	a	b	a	a	b	c
next[j]	-1	0	0	1	1	2

推导过程：

next[0] = -1
j=1：子串 a 无前后缀，next[1] = 0
j=2：子串 ab 最长相等前后缀为 0，next[2] = 0
j=3：子串 aba 最长相等前后缀为 a，长度 1，next[3] = 1
j=4：子串 abaa 最长相等前后缀为 a，长度 1，next[4] = 1
j=5：子串 abaab 最长相等前后缀为 ab，长度 2，next[5] = 2

作用：在 P[j] 失配时，模式串指针回退到 next[j] 继续比较，而主串指针 i 不回溯，从而保证整体 $O(m+n)$ 。

KMP 算法代码实现

// 求 next 数组
void GetNext(char P[], int next[], int n) {
    next[0] = -1;
    int i = 0, k = -1;
    while (i < n - 1) {
        if (k == -1 || P[i] == P[k]) {
            i++;
            k++;
            next[i] = k;
        } else {
            k = next[k];  // 回退
        }
    }
}

// KMP 匹配，S 为主串（长 m），P 为模式串（长 n）
int KMP(char S[], char P[], int next[]) {
    int i = 0, j = 0;
    while (i < (int)strlen(S) && j < (int)strlen(P)) {
        if (j == -1 || S[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];  // 主串不回溯，模式串回退
        }
    }
    if (j == (int)strlen(P))
        return i - j;   // 匹配成功，返回起始位置
    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)$ 。

习题 3

KMP 算法如何避免主串指针回溯？

答案与解析

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

详细步骤：

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

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

上一章节B树及B+树查找介绍B树及B+树的结构、查找过程、复杂度分析及典型习题。

下一章节查找算法分析与应用综合分析各类查找算法的效率、空间复杂度及应用场景，并给出典型综合习题。