如何发明 SAM

如何发明 SAM

我们想做一个结构，接受全部的子串，我们发现，如果考虑增量构造，每次加 1 个字符，增多的字串就是原来的后缀加上这个。

那么我们就这样做。所以我们一直需要一个集合，这些点接受全部后缀。

（以上由红线组成的到根的路径就是我们每个时刻维护的集合，即所有后缀）

那么当在 abc 上加入 b 时，那么我们就在 \([c,bc,abc]\) 上附加一个 b，但是此时我们需要一个 b 才能维护这个集合，但是 b 已经出现过了，它的节点上还有一个额外的 ab，那么我们给他分出来就好了。