字符串匹配

字符串匹配寻找模式在文本中的所有起始位置。朴素方法在每个位置重新比较，但一次失配并不抹掉此前得到的信息；高效算法会复用“已经知道哪些前后缀相等”，由模式自身的重复结构判断可以安全右移多少，或借助哈希、自动机状态避免重复工作。算法选择取决于单模式或多模式、离线或在线、字母表大小，以及是否允许概率碰撞或近似误差。

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

文本 abababa 中模式 aba 出现在位置 $0,2,4$，重叠匹配必须保留。朴素算法最坏 $O(nm)$；KMP 用前缀函数达到 $O(n+m)$，Rabin–Karp 用滚动哈希筛选候选。

空模式、Unicode code point 与字节、大小写归一化都会影响“字符”和位置定义。精确匹配不允许插入删除替换；编辑距离网格理路编辑距离的网格动态规划Levenshtein distance dynamic programming · Wagner–Fischer algorithm把插入、删除与替换写成前缀网格的三类边，求出最小改写费用并重建逐条可执行的脚本。则比较两个整串的最小改写费用。若只允许插删且差异较少，Myers 最短脚本算法理路Myers 最短插删脚本算法Myers O(ND) algorithm · Shortest edit script按插删次数扩展编辑图的最远对角前沿，在差异较小时避免填满网格，并记录蛇形匹配段重建脚本。按编辑次数扩展对角前沿。通配符或正则表达式搜索又需要另行定义允许的模式。

若每个模式位置允许一个明确的字符集合，Shift-And 字符类匹配理路Shift-And 字符类流式匹配Shift-And character-class matching · Shift-And algorithm · 字符类位并行匹配将每个仍然匹配的模式前缀编码为一位，以跨字移位和字符类掩码在线报告全部重叠出现位置。用掩码同时保留所有匹配前缀，支持单符号通配、补类与重叠端点。跨多个字时须传递移位进位并按实际字数计费；把字符类“有交集”直接替换进KMP的字面相等判断，会错误地保留不成立的后缀。

单模式精确匹配中，KMP 算法理路KMP 算法Knuth–Morris–Pratt algorithm利用模式自身前后缀信息避免文本指针回退的线性时间字符串匹配算法。用前缀函数在失配时复用已知边界，给出确定性线性最坏时间；Rabin–Karp 算法理路Rabin–Karp 算法Rabin–Karp algorithm用滚动指纹筛选候选位置并核验相等性的字符串匹配算法。用滚动哈希筛选窗口，必须把碰撞验证和概率假设写入保证；Aho–Corasick 自动机理路Aho–Corasick 自动机Aho–Corasick automaton · AC automaton把模式 Trie 与失败链接结合成一次扫描识别多个模式的确定有限自动机。把模式 Trie 与失败边合并：给它只含 $P$ 的模式集合，就实现这里的单模式接口；保留多个模式时则扩展为报告模式编号与出现位置，扫描时间还要计入输出总数。模式数、是否允许随机碰撞和是否报告全部位置决定应采用哪条路线。

词理路字Word · String从某个有限位置集到字母表的函数，即有限符号序列。提供离散符号序列，数组理路数组Array以连续整数下标支持随机访问的有限序列结构。提供索引表示。KMP、Rabin–Karp 与 Z 函数面向一次或少量模式扫描；Aho–Corasick 预处理模式集合后在线读取文本。以上复杂度通常按文本、模式和实际报告数计，不包含建立固定文本全文索引的成本。

编辑器的“查找全部”需要明确是否保留重叠位置，生物序列检索还要明确字母表与是否允许突变，日志扫描常同时匹配一组告警词，编译器词法分析则按多个 token 模式决定最长合法前缀。它们共享模式匹配内核，却因重叠、近似、多模式与优先级规则不同而需要不同接口，不能只报一个扫描复杂度便视为同一任务。

固定文本上的大量查询可转向后缀树理路后缀树Suffix tree对加入唯一终止符后的全部后缀构造路径压缩 Trie，并以原文本区间表示边标签。，以线性级结构换取沿模式字符导航；Burrows–Wheeler 变换理路Burrows–Wheeler 变换Burrows-Wheeler transform · BWT对带唯一终止符文本的循环移位排序，并取最后一列形成可逆排列。重排文本以暴露可压缩上下文，FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。再叠加 rank 与采样，分别提供 count、locate 和 extract。后两者构成压缩自索引路线，不是把单次 KMP 的 $O(n+m)$ 简单改写成更小空间。