SAM

介绍 首先后缀自动机 可以包括给定字符串的所有子串 O(n) 是自动机 一些定义 endpos 字符串s的一个子串t，endpos(t)为s中t的所有结束位置构成的集合 SAM是一个最小的DFA 有向无环图 节点是状态，边是转移 转移是一些字母 从源点出发到终