广义后缀自动机

参考资料

• 广义后缀自动机 - OI Wiki

简介

广义后缀自动机 是后缀自动机在多个字符串上的推广，能接受一组字符串的所有后缀。把所有串建成一棵 Trie 后在其上构建，或逐串插入时在已有转移处特判，即得一个大小为 $O(\sum|s|)$ 的自动机，可统计多串的本质不同子串等。

例题

洛谷 P6139 【模板】广义后缀自动机（广义 SAM）

给定 $n$ 个仅含小写字母的字符串，求这些字符串中本质不同的子串个数。