字符串匹配String matching

在文本中查找模式的出现位置。单模式与多模式的复用方式不同，还要区分字节、字符或其他符号序列的匹配语义。

怎样选择#

具体算法	问题与前提	时间复杂度	辅助空间	选择与取舍
KMP 字符串匹配	单模式精确匹配	预处理与扫描共 $O(n+m)$	前缀 / 失败函数实现 $O(m)$	前缀表复用失配前的信息，文本指针不回退；模式状态简单。
Aho–Corasick	一组模式在同一文本中匹配	扫描 $O(n+z)$ ，另计构建与转移存储	稀疏自动机约 $O(S)$ ；完整转移表 $O(SR)$	Trie 与失败链接共享模式前缀；模式集、字母表和输出量影响内存与总成本。

左右滑动查看完整对照。点击算法名称，查看原理、约束和实现。