由于本人时间原因，此处只为一个SAM的总结，讨论SAM的基本操作以及性质，详细证明
如要详细学习请查询luogu题解。

算法原理

SAM中每一个节点代表所有结束位置（endpos）相同的串的集合。
每个节点有：1.后缀链接link（到endpos包含它且maxlen最长的那个点，且是为当前点的后缀的点） 2.此点所代表的最长的串的长度（maxlen） 3.走字符 [a-z] 能走到的点（nex[a-z]）

SAM的构造：
设上一个节点为last，当前开一个新节点为cur，当前插入的字符为c。
从last一直走它的link直到走到根节点或某点c的出边不为空，将路径上的所有点的c的出边设为cur。
如果走到根节点说明前面没有和它后缀相同的点，于是将cur的link指向根节点。
否则设走到的点为p，p点c出边指向的点为q。
如果$maxlen(p)+1 = maxlen(q) $,则将cur的link指向q，结束。否则，考虑q的endpos集合的部分后缀并不是cur集合中的串的后缀。此时我们需要新建一个辅助节点clone，复制q的所有信息，并将clone的长度改为$maxlen(p)+1$，再将cur的link指向clone，q的link指向clone。
然而此时还有一个小问题，从cur的link走到的clone并不能由根节点走到clone所代表的endpos的集合，我们需要重定向一些边来使得此性质成立。
于是从p向上走link，将所有当前点c的出边指向q的边重定向到clone，走到第一个点c的出边不指向q的点即可退出。
考虑此时SAM的形态，q的分割为两个集合clone和q，由于clone的maxlen是小于q的，所以clone所代表的所有串是q的后缀。