串与 KMP 模式匹配

概念

串（string，字符串）是由零个或多个字符组成的有限序列。串中任意个连续字符组成的子序列叫子串，包含子串的串叫主串。字符在串中的序号称为该字符的位置。

• 空串：长度为 0，记作 ""。
• 空格串：由空格组成，长度不为 0。" " ≠ ""，这是常考的送分判断题。
• 串相等：长度相同且每个对应位置的字符都相同。

模式匹配（pattern matching）指在主串中定位模式串（子串）首次出现的位置，成功返回首字符位置，失败返回 0（或 −1）。这一节的核心是如何让匹配过程不白走回头路。

原理

朴素算法 BF：失配就整体后移一位

BF（Brute Force，暴力）的做法：主串指针 i 与模式串指针 j 从头比对，相等则双双后移；一旦失配，i 回退到本趟起点的下一个位置，j 回到 1，重开一趟。

主串：  a b a b c a b c a c b a b
模式：  a b a b c a c
        ↑ 前 5 个匹配，第 6 位失配

BF 下一趟（i 回退，j 归 1）：
主串：  a b a b c a b c a c b a b
模式：    a b a b c a c          ← 主串指针回退了 5 次

最坏时间复杂度 O(n × m)（n 为主串长，m 为模式串长）。问题出在回退：主串指针 i 被拉回去重新比对已经看过的字符。

KMP：主串指针永不回退

KMP（Knuth-Morris-Pratt）的核心洞察：失配时，模式串中已经匹配成功的那一段（前缀）本身携带了信息——它的最长相等前后缀告诉我们，模式串可以整体右移多少位而不必重新检查主串。

于是：i 永不回退，只让 j 按 next 数组跳转。

next 数组到底在说什么

next[j] 的含义：当模式串第 j 位与主串失配时，下一趟应当用模式串的第 next[j] 位与主串当前位继续比较。

等价定义（下标从 1 起）：

$$next[j]=max\{k\mid 1\le k<j\text{且}{P}_1\cdots P_{k-1}=P_{j-k+1}\cdots P_{j-1}\}$$

说人话：在 P[1..j−1] 这段里，最长的"既是前缀又是后缀"的串有多长，那个长度 + 1 就是 next[j]。规定 next[1] = 0。

模式 P = a b a a b c a c        (下标 1..8)
对 j=6，看 P[1..5] = a b a a b
        前缀: a | a b | a b a | a b a a
        后缀:               b | a b | a a b | b a a b
        最长相等的是 "ab"，长度 2  →  next[6] = 2 + 1 = 3

nextval：next 的修正版

考虑 P[j] == P[next[j]] 的情形：失配时跳到 next[j] 位，但那一位的字符与原来失配位字符相同，注定再失配一次，白跳。

nextval 规则：

$$nextval[j]=\{\begin{array}{ll}0,& j=1\\ nextval[next[j]],& P_j=P_{next[j]}\\ next[j],& P_j\ne P_{next[j]}\end{array}$$

考试若问"改进后的 next 数组"，指的就是 nextval。

两种下标约定

约定	next[1] / next[0]	关系	常见于
从 1 起	next[1] = 0	—	王道/严蔚敏教材、多数真题
从 0 起	next[0] = -1	next0[j] = next[j] - 1	C 代码实现

写代码用 0 起（数组天然从 0 开始），答题用 1 起（真题默认），两者差 1，务必先声明用哪种。

示例

例：手推 next 与 nextval（模式串 abaabcac）

求模式串 P = a b a a b c a c 的 next 与 nextval 数组（下标从 1 起）。

完整计算过程：

逐位考察 P[1..j-1] 的最长相等前后缀长度 L，则 next[j] = L + 1。

j	P[j]	P[1..j−1]	最长相等前后缀	L	next[j]	判断 P[j] vs P[next[j]]	nextval[j]
1	a	—	—	—	0	—	0
2	b	a	无	0	1	b ≠ a	1
3	a	ab	无	0	1	a = a → 取 nextval[1]	0
4	a	aba	a	1	2	a ≠ b	2
5	b	abaa	a	1	2	b = b → 取 nextval[2]	1
6	c	abaab	ab	2	3	c ≠ a	3
7	a	abaabc	无	0	1	a = a → 取 nextval[1]	0
8	c	abaabca	a	1	2	c ≠ b	2

结论：

下标:    1  2  3  4  5  6  7  8
P:       a  b  a  a  b  c  a  c
next:    0  1  1  2  2  3  1  2
nextval: 0  1  0  2  1  3  0  2

转换为 0 起（代码用）：next0 = [-1, 0, 0, 1, 1, 2, 0, 1]。

C 语言：KMP 与 next 数组构造

#include <stdio.h>
#include <string.h>

#define MAXN 1000

/* 0-based 的 next 数组，next[0] = -1 */
void buildNext(const char *P, int next[]) {
    int m = (int)strlen(P);
    int i = 0, j = -1;
    next[0] = -1;
    while (i < m - 1) {
        if (j == -1 || P[i] == P[j]) {
            i++; j++;
            next[i] = j;              /* 匹配成功：next[i+1] = next[i] + 1 */
        } else {
            j = next[j];              /* 失配：j 回溯，这就是构造的核心 */
        }
    }
}

/* 返回模式串在主串中首次出现的下标，未找到返回 -1 */
int kmp(const char *S, const char *P) {
    int n = (int)strlen(S), m = (int)strlen(P);
    int next[MAXN];
    buildNext(P, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == P[j]) { i++; j++; }
        else j = next[j];             /* 主串指针 i 不动 */
    }
    return (j == m) ? i - m : -1;
}

int main(void) {
    char P[] = "abaabcac";
    int next[MAXN];
    buildNext(P, next);
    for (int i = 0; P[i]; i++) printf("%d ", next[i]);
    printf("\n");                                     /* -1 0 0 1 1 2 0 1 */
    printf("%d\n", kmp("ababcaabaabcacbab", "abaabcac"));  /* 6 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

def build_next(p):
    """0-based next，next[0] = -1"""
    m, nxt = len(p), [-1]
    i, j = 0, -1
    while i < m - 1:
        if j == -1 or p[i] == p[j]:
            i += 1; j += 1
            nxt.append(j)
        else:
            j = nxt[j]
    return nxt

def kmp(s, p):
    nxt, i, j = build_next(p), 0, 0
    while i < len(s) and j < len(p):
        if j == -1 or s[i] == p[j]:
            i += 1; j += 1
        else:
            j = nxt[j]
    return i - j if j == len(p) else -1

print(build_next("abaabcac"))                  # [-1, 0, 0, 1, 1, 2, 0, 1]
print(kmp("ababcaabaabcacbab", "abaabcac"))    # 6

# 1-based next 的手算版（对照用）
def next_1based(p):
    m = len(p)
    nxt = [0] * (m + 1)
    for j in range(2, m + 1):
        sub = p[:j - 1]
        best = 0
        for L in range(1, len(sub)):
            if sub[:L] == sub[-L:]:
                best = L
        nxt[j] = best + 1
    return nxt[1:]

print(next_1based("abaabcac"))                 # [0, 1, 1, 2, 2, 3, 1, 2]

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• BF 最坏 O(n × m)；KMP 时间复杂度 O(n + m)，其中构造 next 为 O(m)，匹配为 O(n)。
• KMP 的关键性质：主串指针 i 永不回退，回退的只有模式串指针 j。
• next[j] 只与模式串自身有关，与主串无关，所以可以预处理。

2. next 数组的下标陷阱（失分第一来源）

• 1 起：next[1] = 0，数组值为 [0,1,1,2,2,3,1,2]（以 abaabcac 为例）。
• 0 起：next[0] = -1，数组值为 [-1,0,0,1,1,2,0,1]。
• 题目不给下标约定时，答案相差 1 就全错——答题第一步先写"以下采用下标从 1 起"。

3. 易错点

• next 求的是 P[1..j−1] 的最长相等真前后缀，不能把整段自己算进去（那是 j−1，不是答案）。
• 求 nextval 时若 P[j] == P[next[j]]，要递归地取 nextval[next[j]]，不是直接取 next[next[j]]（虽然结果常一样，但规则要写对）。
• "KMP 消除了主串的回溯"是匹配阶段的结论；构造 next 时模式串指针 j 是要回溯的，不要混为一谈。
• 空串是任意串的子串；空串长度 0，空格串长度大于 0。
• 若主串长 n、模式串长 m，匹配失败时至少需要 n − m + 1 趟比较（BF），这是选择题常问的"最多比较趟数"。

小结

• 串是特殊的线性表，其"数据元素"限定为字符，操作以整体（连接、求子串、定位）为主。
• BF 的毛病是主串指针回退；KMP 用最长相等前后缀信息换掉了这个回退。
• next[j] = P[1..j−1] 的最长相等前后缀长度 + 1；nextval 是对"跳过去必然再失配"的修正。
• 手推 next 是历年选择题的常客，务必自己能完整推出一遍。

下一篇：树与二叉树