形式陈述

精确字符串匹配给定文本 $T[0..n-1]$ 和模式 $P[0..m-1]$，寻找所有位移 $s$，使

$$T[s..s+m-1]=P[0..m-1].$$

朴素算法逐位移比较，最坏 $O((n-m+1)m)$。KMP 预处理模式的最长真前缀—后缀信息，使失配后复用已知匹配而不回退文本指针，预处理 $O(m)$、扫描 $O(n)$。有限自动机、Z 算法和 Rabin–Karp 也提供不同时间/空间或随机化权衡。

直觉

失配并不抹掉此前比较得到的信息；模式自身的重复结构决定它可以安全向右移动多少，而无需重查文本。

例子与边界

模式 ababaca 的前缀函数记录每个前缀可与自身后缀重合的最长长度，KMP 失配时沿这些 border 回退。Rabin–Karp 用滚动哈希筛选候选位置，若不再逐字符验证，会有碰撞概率。精确匹配不同于允许编辑距离的近似匹配，也不同于正则表达式匹配。空模式出现位置的约定应由接口明确。

推论与应用

字符串匹配用于编辑器搜索、生物序列、日志扫描和编译器。多模式任务可用 Aho–Corasick，后缀数组/树适合固定文本上的大量查询。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 32, exact string matching and KMP。
• Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997，Chs. 1–2, borders, prefix matching, and linear algorithms。