基本术语

前缀与后缀

字符串是线性连续的数据序列。为避免索引歧义，通常用半开半闭区间 [i,j)[i, j) 表示字符串片段，其中包含起始索引 ii，不包含终止索引 jj。

设字符串 SS 长度为 nn，有效索引区间为 [0,n)[0, n)。

字符串有两类特殊子串：前缀与后缀。前缀 S.prefix(k)S.prefix(k) 表示从起始位置开始、长度为 kk 的片段，等价于 S.substr(0,k)S.substr(0, k) 或 S[0,k)S[0, k)。后缀表示最后 kk 个字符组成的子串：

任意内部子串都可以表示为某个前缀的后缀，或某个后缀的前缀：S.substr(i,k)=S.prefix(i+k).suffix(k)=S.suffix(n−i).prefix(k)S.substr(i, k) = S.prefix(i + k).suffix(k) = S.suffix(n-i).prefix(k)。这种区间恒等关系为后续复用已知匹配信息提供了基础。

抽象数据类型接口

字符串抽象数据类型（ADT）提供标准操作接口，支持属性获取、子串截取、拼接和模式搜索等操作。

应用实例

以主字符串 "data structures" 为例，length() 返回 1515。在零起点索引下，charAt(5) 返回字符 's'。prefix(4) 截取首部片段 "data"；suffix(10) 从尾部截取，得到 "structures"。

在涉及多个字符串的运算时，"data structures".concat(" & algorithms") 会在内存中申请新的空间，拼接生成 "data structures & algorithms"。若对不同字符串进行严格一致性判定，"algorithms".equal("data structures") 将返回逻辑假 false。

对于核心的模式检索，若在文本 "data structures and algorithms" 中调用 indexOf("string")，由于该子序列未在主序列中出现，函数将返回状态码 -1 表示未命中。若调用 indexOf("algorithm")，检索过程将在主串索引 2020 处完成匹配，并返回该整型位置数据。

字符串匹配

循模式访问

模式匹配算法的性能依赖输入分布。设文本串 TT 长度为 nn，模式串 PP 长度为 mm。典型场景通常满足 2≪m≪n2 \ll m \ll n，即模式串有一定长度但远短于文本。

对该过程进行随机性建模，假定可用字符集的规模为 s=∣Σ∣s = |\Sigma|。在文本串与模式串均为随机独立生成的条件下，任意两个单一字符比对成功的概率为 s−1s^{-1}。当要求模式串整体对齐时，连续 mm 个字符均能顺利匹配的先验概率 PrmatchPr_{match} 会呈现指数级衰减，近似等价于 n⋅s−mn \cdot s^{-m}。随着字符集 ss 的增大或模式长度 mm 的增加，该概率值 PrmatchPr_{match} 迅速趋近于 00。

这一概率特性说明：大多数对齐位置会在较早字符处失配。因此，优化重点不是加速少数成功匹配，而是低成本处理大量失配，并尽量增加下一次尝试的位移。

蛮力匹配

最直接的方案是蛮力匹配：将模式串起点依次与文本串各位置对齐并逐字检查。一旦字符失配，就判定当前对齐无效，将模式串右移一位并重新比较。

蛮力算法的第一种实现形式采用显式的双指针并行递增架构。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 返回模式串 P 在文本串 T 中首次出现的位置；未匹配则返回 -1。
int match(const char *P, const char *T) {
    // n 是文本长度，m 是模式串长度。
    const size_t n = strlen(T), m = strlen(P);
    // 空模式串按惯例匹配文本起点。
    if (m == 0) return 0;

    // i 指向文本串 T，j 指向模式串 P。
    size_t i = 0, j = 0;
    // 当模式串未完全匹配且文本未扫描完时继续比较。
    while (j < m && i < n)
        if (T[i] == P[j]) {
            // 当前字符匹配，两个指针同步前进。
            i++;
            j++;
        }
        else {
            // 失配时，i - j 是本轮对齐起点；下一轮从起点后一位重新对齐。
            i = i - j + 1;
            // 模式串从首字符重新开始比较。
            j = 0;
        }
    // j 到达 m 表示完整匹配，起点为 i - j。
    return (j == m) ? (int)(i - j) : -1;
}

变量 ii 和 jj 分别是文本串 TT 与模式串 PP 的游标。若 T[i] == P[j]，二者同步前移；若失配，则执行 i = i - j + 1，将文本游标回到本轮起点的下一位，并将模式串游标 jj 归零。该回退机制在大量局部匹配场景中会导致重复读取。

第二种实现形式使用标准的双层嵌套循环，外层负责穷举对齐点，内层负责验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 双层循环形式的蛮力匹配。
int match(const char *P, const char *T) {
    // n 是文本长度，m 是模式串长度。
    const size_t n = strlen(T), m = strlen(P);
    // 空模式串默认匹配文本起点。
    if (m == 0) return 0;
    // 模式串长于文本时不可能匹配，并避免 n - m 的无符号下溢。
    if (m > n) return -1;

    // i 枚举对齐起点，j 枚举模式串内部偏移。
    size_t i = 0, j = 0;
    // 最后一个合法起点是 n - m。
    for ( i = 0; i < n - m + 1; i ++ ) {
        // 在当前起点 i 上逐字符验证 P。
        for ( j = 0; j < m; j++)
            // 任一字符失配，则当前对齐失败。
            if (T[i+j]!= P[j]) break;
        // j 扫过整个模式串，表示已经完全匹配。
        if (m <= j) break;
    }
    // 完整匹配返回起点 i，否则返回失败标记。
    return (j == m) ? (int)i : -1;
}

外层 for 将起始对齐位置 ii 限定在 [0,n−m+1)[0, n-m+1)，避免模式串越界；若模式串长于文本串，则提前返回 -1，避免无符号整数下溢。内层通过偏移 i+ji+j 访问文本串，失配时 break 并进入下一对齐位置。该写法没有显式回退文本指针，但计算量与第一种实现等效。

时空复杂度

蛮力策略只依赖标量游标，空间复杂度为 O(1)\mathcal{O}(1)。时间复杂度取决于字符序列：最优情况下，模式串首字符很少匹配文本，内层比较很快结束，整体接近 Ω(n)\Omega(n)；最坏情况下，文本和模式串存在大量相同前缀，只在末尾失配，每次对齐都会重复扫描较长片段，复杂度退化为 O(n⋅m)\mathcal{O}(n \cdot m)。在大规模文本流中，文本指针回退还会破坏顺序读取。

KMP 算法

状态不变性

要突破二次复杂度，需要利用扫描过程中的状态不变性。假设某一时刻文本指针 ii 与模式指针 jj 正在比较，且此前 jj 个字符均已匹配，则有区间等式：T[i−j,i)==P[0,j)T[i-j, i) == P[0, j)。

该不变量表示：算法已经知道文本片段 T[i−j,i)T[i-j, i) 与模式串前缀 P[0,j)P[0, j) 完全相同。蛮力算法的问题在于，失配后丢弃了这段已知信息，并从下一个对齐位置重新试错。

一旦 T[i]T[i] 与 P[j]P[j] 失配，理想策略是保持文本指针 ii 不回退，只在模式串内部寻找新的位置 tt。该位置需要满足更短前缀 P[0,t)P[0, t) 可以对接当前已知文本后缀。由于已知文本后缀等价于模式串后缀，问题转化为模式串内部前后缀性质的预处理。

为避免 ii 回退，匹配成功时双指针同步右移；在 P[j]P[j] 处失配时，不复位 ii，而是将模式串指针 jj 更新为更小的 tt，然后比较 T[i]T[i] 与新的 P[t]P[t]。

状态变量 tt 可以只根据模式串前缀性质离线预处理得到。无论失配发生在位置 jj，都可查询一维状态转移表 next[0, m) 获取新位置。next[j] 表示第 jj 位失配时模式串应跳转到的有效状态。该表用额外空间减少重复扫描，使模式串在失配时可一次右移多个位置。

next[j] 不是“下一位要比较谁”，而是“当模式串第 j 位失配时，已经匹配的前 j 个字符最多还能保留多少个”。文本指针 ii 不回退，模式串指针 jj 回退到 next[j]，等价于把模式串整体右移，但不重新读取文本中已经确认过的字符。

状态表实例

以模式串 CHINCHILLA 为例说明 next 数组构造。

针对长度为 10 的字符集，各前缀的转移状态记录如下：

索引 j 0 1 2 3 4 5 6 7 8 9
字符 P[j]P[j] C H I N C H I L L A
跳转状态 next[j] -1 0 0 0 0 1 2 3 0 0

在该实例中，当 j=7j=7（字符 L）失配时，其前置子串 CHINCHI 包含长度为 3 的相同前后缀 CHI，因此 next = 3。该表用于确定回退位置，并尽量增大模式串位移。

KMP 算法依赖预先构建的 next 数组。主干如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// KMP 主匹配过程：文本指针 i 不回退，模式串指针 j 按 next 表回退。
int match(const char *P, const char *T) {
    // m 是模式串长度。
    int m = (int)strlen(P);
    // 空模式串默认命中文本起点。
    if (m == 0) return 0;

    // 预处理模式串失效函数。
    int * next = buildNext(P);
    // n 是文本长度，i 是文本指针。
    int n = (int)strlen(T), i = 0;
    // j 是模式串当前状态。
    int j = 0;
    // 未完整匹配且文本仍有字符时继续。
    while (j < m && i < n)
        if (0 > j || T[i] == P[j]) {
            // j == -1 或当前字符匹配时，文本指针前进。
            i++;
            // 模式串进入下一状态；j == -1 时会回到 0。
            j++;
        } else {
            // 失配时只回退模式串状态，不回退文本指针。
            j = next[j];
        }
    // 释放预处理数组，避免内存泄漏。
    delete[] next;
    // j == m 表示完整匹配，起点为 i - j。
    return (j == m) ? (i - j) : -1;
}

程序先调用 buildNext 建立转移表。主 while 循环中，0 > j 用于处理边界状态。当模式串指针退回 -1 时，表示模式串首字符已失配，且没有可用前后缀可复用；此时进入 if 分支，使 jj 回到 00，同时 ii 前进一位。循环结束后释放 next 数组；只有 j=mj=m 时返回起点 i−ji-j，否则返回 -1。

由于文本指针不回退，KMP 适合顺序数据流或不便回放的文本缓冲区。

主循环的进度可以看成由 ii 驱动。成功匹配时 ii 前进；第一个字符都不匹配时，j == -1 也会推动 ii 前进；中间失配时只有 jj 后退，ii 留在原地等待新的模式串状态来比较同一个文本字符。于是文本串从左到右只被扫描一遍。

模式串与 DFA

KMP 可将每个模式串等效编译为一个确定性有限自动机（DFA）。模式串决定状态机结构，状态数为模式串长度加一，转移由输入字符控制。

若不采用查表方式，也可以将特定模式串（如 chinchilla）转译为分支代码，用 goto 模拟状态转移。逻辑结构如下：

在这种特化的指令集流中，文本指针 ii 在每一步只执行单调递增。若当前字符匹配，指令顺序进入下一状态代码块；若失配，则依据预先计算好的最长公共前后缀边界，通过硬编码的 goto 指令将控制流发配至上游的特定代码块。这证实了模式串预处理实际上是一种针对有限状态转换矩阵的内联优化过程。

失效函数

KMP 的关键在于准确构造状态数组。定义位置 jj 的边界集合 N(P,j)N(P, j)：它包含所有使模式串前缀 P[0,t)P[0,t) 与以 jj 结尾的后缀 P[j−t,j)P[j-t,j) 相等的非负长度 tt：∀j≥1,N(P,j)={0≤t<j∣P[0,t)=P[j−t,j)}\forall j \ge 1, \quad N(P, j) = \{ 0 \le t < j \mid P[0, t) = P[j-t, j) \}。

该集合表示所有合法重合长度。为避免漏过潜在匹配，需要选择其中最大元素作为回退位置：next[j]=max⁡{N(P,j)}next[j] = \max \{ N(P, j) \}。边界条件设为 next[0]=−1next[0] = -1。

若直接用朴素方法计算所有前缀的边界集合，复杂度较高。由于 N(P,j)N(P, j) 依赖字符串线性延续性，可以利用递归传递关系优化。

假定已知当前序列在第 jj 位的最长边界为 t=next[j]t = next[j]。这意味着 P[0,t)=P[j−t,j)P[0, t) = P[j-t, j)。随后考察下一位字符。如果 P[j]==P[t]P[j] == P[t]，那么原有的前后缀相等关系可以向右无缝延伸一个单位。此时必然得出递推等式：next[j+1]=next[j]+1next[j+1] = next[j] + 1。

若 P[j]≠P[t]P[j] \ne P[t]，需要寻找更短的候选边界。由于已有 P[0,t)==P[j−t,j)P[0, t) == P[j-t, j)，寻找当前序列更短边界等价于在前缀串 P[0,t)P[0, t) 内寻找最大边界。因此将候选长度缩短为 next[t]next[t]，并继续比较新的 P[next[t]]P[next[t]] 与 P[j]P[j]。该过程称为模式串的自匹配。

构造 next 时，变量 j 相当于“正在扩展的后缀末端”，变量 t 相当于“当前候选前缀长度”。如果 P[j] 和 P[t] 能接上，边界长度就增加；如果接不上，就把候选长度缩短为 next[t]。这和匹配阶段失配时缩短 j 是同一套思想，只不过此时文本串换成了模式串自己。

依据自匹配实效函数构造算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 构造 KMP 失效函数 next；N[j] 表示 P[j] 失配时应回退到的状态。
int * buildNext(const char *P) {
    // m 是模式串长度。
    int m = (int)strlen(P);
    // 空模式串没有可构造的状态表。
    if (m == 0) return nullptr;

    // N 保存每个位置的最长真前后缀长度。
    int * N = new int[m];
    // j 是当前正在扩展的位置，t 是当前候选边界长度。
    int j = 0, t = -1;
    // 第 0 位失配时没有可保留前缀，使用 -1 触发文本指针前进。
    N[0] = -1;
    // 逐步构造 N[1] 到 N[m - 1]。
    while (j < m - 1)
        if (0 > t || P[j] == P[t]) {
            // 当前候选边界可以延伸一位。
            ++j;
            ++t;
            // 记录 P[0, j) 的最长真前后缀长度。
            N[j] = t;
        } else {
            // 当前候选无法延伸，退到更短候选边界继续尝试。
            t = N[t];
        }
    // 返回由调用者释放的动态数组。
    return N;
}

迭代中，jj 表示当前处理位置，tt 表示当前候选前缀边界长度。由于 tt 可能为 −1-1，0 > t 用于处理重新起步的边界情况。

以模式串 MAMAMMIA 为例，追踪此迭代过程，未经过优化的原始失效边界计算将生成以下序列特征：

j 0 1 2 3 4 5 6 7
P[j] M A M A M M I A
未优化边界 -1 0 0 1 2 3 1 0

上述计算得出的实质是原始的失效函数 f[j]f[j]。为了进一步消除多余的回退，若查表发现当前字符与回退后的字符相同（即 P[j]==P[t]P[j] == P[t]），意味着采用该回退必然导致再次失配。于是代码中可以加入判定：若相等，则继承更深层的跳转地址，即将 N[j]N[j] 直接赋值为新位置 tt 所存储的回退值，从而形成一步到位的最终 next 数组。

复杂度分析

KMP 主循环中可能出现多次 next 回退，因此需要证明整体不会退化到 Ω(n⋅m)\Omega(n \cdot m)。

定义势函数 k=2⋅i−jk = 2 \cdot i - j，分析循环分支对 kk 的影响：

  1. 成功匹配分支： 当 0>j0 > j 或 T[i]==P[j]T[i] == P[j] 成立时，执行语句 i++; j++;。在此状态转移下，新势能等于 2(i+1)−(j+1)=2i−j+12(i+1) - (j+1) = 2i - j + 1。较原势能 kk，增量严格为 +1+1。
  2. 失配回退分支： 当触发 j = next[j] 时，文本指针 ii 保持不变，且根据底层结构定义，下一跳状态必定小于当前状态（next[j]<jnext[j] < j）。因此减数项 jj 缩小，导致总体势能 2i−j2i - j 必然增大。由于 jj 为整数，其增量至少为 +1+1。

因此，无论执行哪个分支，势函数 kk 都单调递增。初始时 k=0k = 0。当算法终止时，文本游标最大为 n−1n-1，模式串回退最小为 −1-1，所以全局势能上界为：kmax=2⋅i−j≤2(n−1)−(−1)=2n−1k_{max} = 2 \cdot i - j \le 2(n-1) - (-1) = 2n - 1。

由于 kk 每轮至少增加 11，且上界为 2n−12n-1，主 while 循环总轮数为 O(n)\mathcal{O}(n)。同理，构造 next 数组需要 O(m)\mathcal{O}(m)。因此，KMP 总时间复杂度为 O(n+m)\mathcal{O}(n+m)。