考研 408 · 字符串核心知识点

考研 408 · 字符串核心知识点

408 中字符串以 模式匹配（朴素 / KMP） 为绝对重点，配合字符串存储与基本操作。

1. 字符串的存储

顺序存储：char s[MAXLEN]，用 '\0' 或 length 记录长度
堆分配：char* s，长度动态管理
块链存储：链表每个结点存多个字符（块），省指针空间

408 约定：字符数组下标常从 1 开始（s[1..n]），便于 next 数组推导；下标 0 存长度或不用。

2. 朴素模式匹配（BF）

主串 s（长 n）、模式串 p（长 m）：

从主串每个位置 i 起，与 p 逐位比较；
失配则 i 回退到 i+1，j 回到 1，继续。

时间复杂度：最坏 O(n·m)；平均 O(n+m)。

图示

主串: a b a b c a b
模式: a b c

第 1 趟: a b a  失配于 c vs a → 主串从第 2 位再来
第 2 趟:   a b a
第 3 趟:     a b c ✓ 匹配成功，位置 3

3. KMP 算法

核心思想

失配时主串不回溯，模式串沿 next 数组滑动，把已匹配前缀的信息利用起来。

int KMP(const char s[], const char p[]) {
    int i = 1, j = 1;
    while (i <= s[0] && j <= p[0]) {
        if (j == 0 || s[i] == p[j]) { i++; j++; }
        else j = next[j];
    }
    if (j > p[0]) return i - p[0];  // 匹配位置
    return 0;
}

next 数组定义（next[1] = 0）

next[j] = 模式串 p[1..j-1] 中"最长相等前后缀长度 + 1"
失配时 j = next[j] 再比。

求解 next（递推）

void getNext(const char p[], int next[]) {
    int j = 1, k = 0;
    next[1] = 0;
    while (j < p[0]) {
        if (k == 0 || p[j] == p[k]) {
            j++; k++; next[j] = k;
        } else {
            k = next[k];
        }
    }
}

图示（p = a b a b a a）

j   : 1  2  3  4  5  6  7
p   : a  b  a  b  a  a  -
next: 0  1  1  2  3  4  2

例：j=5 时 p[1..4] = a b a b，最长相等前后缀 "ab" 长 2 ⇒ next[5] = 3

nextval（优化 next）

若 p[j] == p[next[j]]，则 nextval[j] = nextval[next[j]]，进一步跳过相同字符比较。

时间复杂度：O(n+m)；空间 O(m)。

4. 常用题型

5. 例题速览

例 1：主串 ababcabcacbab，模式 abcac，求 next 数组并用 KMP 找首次匹配。

p   : a b c a c
next: 0 1 1 1 2
比较过程：
  a b a b c a b c a c a b
  a b c        失配(c vs a) → j = next[3] = 1
    a b c a c  匹配成功，位置 6

例 2：next[7] 语义 = 当第 7 位失配时，模式串从第 next[7] 位继续比较。

6. 易错点

• next 数组下标从 1 开始、next[1]=0；
• 前缀/后缀都是真子串（不含自身）；
• KMP 主串指针只增不减；
• 朴素匹配最坏情况如 s=aaaaab, p=aaab。

下一篇：树

Read Also

• 考研 408 · 树核心知识点