月度归档： 2019年6月

后缀自动机（Suffix Automation, SAM）是一种能够接受所有源串后缀的最简的DFA（确定性有限状态自动机）．他的定义使得他具有以下性质：

• 最简
• 是一个有向无环图（DAG），点之间的单向边即为字符的转移
• 有且仅有源串的所有子串可以在这张图上走到一个节点，一个节点可能对应多个子串，这些子串的各个结束位置均完全一致
  （这些字符串接下来的任何转移均完全相同．为了最简，这些状态会被合并）
  
• 时间、空间复杂度均在\(O(n)\)级别（这个需要证明）

继续阅读“后缀自动机”