[deleted]
字节营d5后猛然发现队里只有一个人会后缀科技，不是很妙的样子。。。，，救一下
轻轻敲醒沉睡的心灵
SDOI2016 生成魔咒
\(\sum len[i]-len[par[i]]\)
TJOI2015 弦论
sam从根的一条路径是一个子串，第k小就串dp一下然后从根模拟地走
AHOI2013 差异
sam两个串的lcp是lca的len。枚举lca
HAOI2016 找相同字符
两个串建广义sam，然后\(\sum (len[i]-len[par[i]])\times si[0][i]\times si[1][i]\)，\(si\)表示两个串在\(i\)这个点的rightpos大小
USACO17DEC Standing Out from the Herd P
一起建广义sam，然后par树合并一下可以知道每个节点下面有那些串
ZJOI2015 诸神眷顾的幻想乡
20个叶子，枚举一个，把树重整理成trie，加入广义sam。最后\(\sum len[i]-len[par[i]]\)
NOI2018 你的名字
对S先sam+线段树合并，然后维护一个“当前匹配长度”\(len\)，在S的sam上跑T的匹配，跑的时候通过检查\(rightpos\)里有没有\([ql+len,qr]\)内的元素来判断能不能走，，不能走就把\(len--\)，同时如果\(len\)进入了par的表示范围，就跳到par。这样就知道T的每个位置最长匹配\(S[ql,qr]\)多长。最后扫一遍T的sam，然后T的sam每个节点随便找一个出现的pos，检查一下这个节点表示的子串中有没有S匹配不出来了，加上去。
CF1063F String Journey
倒过来，递减变递增。先贪心，分割串长可以是逐步加1的。设\(dp[i]\)表示，考虑前i，然后最后一个分割串强制是\(s[1...i]\)的后缀，最长划分包含几个分割串。显然\(dp[i-1]+1\ge dp[i]\)，因为i的方案丢掉i就能得到一个i-1的方案。据此可以暴力地进行dp: 直接枚举dp[i]是多少，然后去sam+线段树合并上面看行不行，不行就dp[i]--。
这题有个优雅的根号+哈希的暴力，很nb。看洛谷题解吧。
CF700E Cool Slogans
经典仙人题hh。首先小贪心一波，每个串的前面那个串都让他是自己串的后缀，所以par树从上往下dp。一个nb结论是，如果u是v在par树上的祖先，那么u代表的所有串在v代表的最长串的匹配情况都一样。因为u代表的串都是等价类，如果v能匹配等价类里短的匹配不了长的，说明v应该更长。这样说明sam里同一个点管的等价类在dp中都等效，那直接拿每个点最长的串dp。后面转移check都是套路随便弄反正带个log也没事。
慢慢睁开你的眼睛
CTSC2012 熟悉的文章
二分答案，后面是个简单的单调队列dp。但是需要求出每个位置的后缀在字符串库中的match长度。直接广义sam跑。
CF666E Forensic Examination
好nb的比赛数字，不过西方文化里666好像是恶魔的意思，不太吉利。。这题对T建广义sam，按串id做下标维护出现次数的线段树合并。把S在exsam里面跑，每个位置跑到的点是哪个记录下来。询问的时候，从pr对应的sam点倍增往上跳，跳到长度满足pr-pl+1为止。然后线段树查询一下。注意特判出现次数为0，此时要输出l。
区间本质不同子串个数
离线询问，枚举r，维护每个l的答案。当r加1，实际上是把par树到根的所有点的lastpos设成r，对应到ans[l]里面是一个等差数列加。用lct可以维护这个过程，等差数列加再写个线段树。