构建其实也写了，但没放上来
直接放题吧
【模板】后缀自动机（SAM）
首先我们求出SAM
然后，我们对于每一个前缀对应的节点的edp+1，因为这个串是最长的串（为叶子）
然后dfs子树求和，求出edp，然后就可以做了
P2408 不同子串个数
SAM中一个节点代表的串的个数是\(len[now]-len[link[now]]\)，对于每个节点分别求和
P4070 [SDOI2016] 生成魔咒
和上面的一样，不过要动态维护
由于每次只会改变常数个点，直接维护那个ans即可
P5341 [TJOI2019] 甲苯先生和大中锋的字符串
出现次数就是edp集合的大小
然后对于每一个节点看，如果正好k次，就对最长长度和最短长度之间差分一下然后扫一遍即可
CF802I Fake News (hard)
和模板几乎一模一样
P3975 [TJOI2015] 弦论
比较有意思
(待补)
P6640 [BJOI2020] 封印
首先把T串建SAM，对于每个S的前缀算出在T中出现过的最大后缀长度slen
查询就是\(\min_{i=l}^r min(i-l+1,slen_i)\)
假设\(i-l+1<=slen_i\),也就是\(i-slen_i+1<=l\)
可以发现，随着i的增加，左边的一定是非严格单调递增的，因为i每次会增加1，slen最多增加1
那么就可以二分出最小的i满足上述条件，那么左边的就是\(i-l+1\),右边的就是slen
左边的就用i算，右边的用ST表求最小值即可
CF235C Cyclical Quest
首先还是把文本串建出，求出每个节点edp的大小，设为siz数组
然后由于循环同构，就可以看成删除一个前面的，添加一个后面的
那么先把T能匹配匹配，然后如果长度大于了len，就删一个前面的
每次增加一个后面的
删就用上SAM的性质，因为parent树就是减前缀，每次减一后看要不要跳fa
如果匹配的长度等于T的长度就累加siz即可