字符串模式匹配查找

定义与基本思想

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

常见算法

朴素算法（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 数组的步骤

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

示例：模式串 “abaabc”

推导过程：

• 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 算法的基本思想及其优点。

习题 2

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

习题 3

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