字符串匹配

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

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

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

空模式、Unicode code point 与字节、大小写归一化都会影响“字符”和位置定义。精确匹配不允许插入删除替换；带编辑距离、通配符或正则表达式的搜索属于更广模型。

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

词公理库字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)$ 简单改写成更小空间。