后缀自动机

• \(root\) 到 \(x\) 的 fail 树上的每个父亲的路径并起来是 \(s[1...x]\) 的所有本质不同后缀
• sam 上根到每个点的路径对应着所有本质不同的子串
• \(1\to fail[x]\) 是 \(1\to x\) 的后缀