字符串算法

KMP 的失配函数、Z 算法、Rabin-Karp 滚动哈希、后缀数组/后缀自动机、AC 自动机。本章还讲正则表达式引擎的两种实现（NFA 模拟与回溯）及其性能差异。

本章要点

• KMP 的核心是”前缀的后缀”
• 滚动哈希让子串比较 O(1)
• 回溯式正则引擎存在指数级最坏情况（ReDoS）

相关阅读

• 有限自动机与正则语言

写作状态

本章目前为提纲，正文待撰写。