由于本人时间原因，此处只为一个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的后缀。

性质

每个点所代表的是endpos相同的一个集合，串的长度是连续的，且区间在\([maxlen(link[now])+1,maxlen(now)]\),其中的短串为长串的后缀。
从根节点出发能走出所有的子串，走后缀链接能走到所有为当前点后缀的点。
link构成的树是后缀树。
待补