说明
以个人学习经历来说，这两篇写的最透彻。
难度大致按照升序排列，SAM和广义SAM都有。
广义SAM的写法一定要正确，否则不能按照 (mxlen) 拓扑排序。
个人感觉：SAM需要非常扎实的DS基础。恶心的SAM需要大力DS，比较重工业。很多SAM需要线段树合并维护endpos。常用的东西比如SAM板子，线段树合并板子，LCT板子必须一遍打对，否则根本没时间查。
本文大概写了一些SAM经典题以及简要题解。
例题
P3804 【模板】后缀自动机 (SAM)
我们知道SAM上每个结点对应一个endpos，而endpos的大小就是这个串的出现次数。考虑在每一个字符插入结束的节点打tag，基数排序得到拓扑序，按照逆拓扑序更新每个节点的endpos大小。最后统计 (cnt_i>1) 的节点中， (cnt_i imes mxlen_i) 的最大值即可。如果理解不了基数排序也可以显式建树，直接维护子树大小。评测记录
P2408 不同子串个数
建出SAM，求出 (sum mxlen_i-mxlen_{link_i}) 即可，即每一个节点包括的状态数总和。一个节点的状态数为 (maxlen(i)-minlen(i)+1=mxlen[i]-(mxlen[link[i]]+1)+1=mxlen[i]-mxlen[link[i]])。评测记录
P6139 【模板】广义后缀自动机（广义 SAM）
建出广义SAM，其余同上 评测记录
如果你有兴趣可以来一发*倍经验
SP694 DISUBSTR - Distinct Substrings
SP705 SUBST1 - New Distinct Substrings
SP1811 LCS - Longest Common Substring
- SP1812 LCS2 - Longest Common Substring II
- SP10570 LONGCS - Longest Common Substring
- P5546 [POI2000]公共串
四倍经验三紫一黑
太像了就放一起说了
解法1：建广义SAM。每一个点可以状压打个标记。维护endpos集合种类数即可。所有种类都出现的串中取最大的 (mxlen) 即可。
解法2：对第一个串建SAM。让后面的串沿着SAM跑，维护到每一个节点最大的匹配长度，然后在后缀树上从下往上传信息，每个节点的最终最大匹配长度为 (max(match[u],min(match[v],mxlen[u])))。
P4070 [SDOI2016]生成魔咒
动态往后加字符直接上SAM。每新增一个节点 (np) 加上 (mxlen[np]-mxlen[p]) 即可。但是 (nq) 不用增，因为 (nq) 被插到 (q) 与 (link[q]) 之间， (mxlen[q]-mxlen[link[q]]=mxlen[q]-mxlen[nq]+mxlen[nq]-mxlen[link[q]])。这种字符集比较大的可以拿 (map) 存转移边。评测记录
P3975 [TJOI2015]弦论
SAM上手好题。最后大概是让一个指针按照字典序沿着转移边跑，维护每一个节点的大小，即有多少个串以它为前缀，然后就可以递归跑了。
相同子串算一个：每个结点的 (siz) 设 (1) 即可。
相同子串算多个：每个节点的 (siz) 为 (endpos) 大小。
P3346 [ZJOI2015]诸神眷顾的幻想乡
叶子不超过 (20) 个提示明显。直接以每一个叶子为根，从其余叶子往上跑，形成 (380) 个 (1e5) 的字符串，全丢进广义SAM，求本质不同子串个数即可。发现空间并不能开串长乘2。发现根本没法卡满。自己最大把自己卡到 (O(20n)) ，就开了这么大，AC了。评测记录
P4081 [USACO17DEC]Standing Out from the Herd P
直接建广义SAM。对于每一个节点打标记，看看哪些编号的字符串在它子树内。不止一种就不用统计贡献，否则加上它的状态数 评测记录
P5341 [TJOI2019]甲苯先生和大中锋的字符串
首先建SAM，维护出endpos集合大小。如果大小为 (k) 那么 ([minlen(i),maxlen[i]]) 内都会产生贡献。(minlen(i)=mxlen[link[i]]+1) ，直接差分即可。trick:多测可以动态开点。评测记录
CF802I Fake News (hard)
首先建SAM，维护出endpos集合大小。那么 (ans=sum cnt_i^2 (mxlen[i]-mxlen[link[i]])) 。因为这个节点代表的状态都出现了 (cnt_i) 次，乘上 (cnt_i^2) 即可。评测记录
CF452E Three strings
首先把三个串丢进广义SAM。对于每一个节点我们可以知道它在每一个串中的出现次数，分开统计三个串的endpos集合大小即可。那么对于 ([minlen(i),maxlen(i)]) 都会产生 (cnt_{i,0} imes cnt_{i,1} imes cnt_{i,2}) 的贡献，差分即可。评测记录
SP8093 JZPGYZ - Sevenk Love Oimaster
重要结论：SAM上暴力跳链是 (O(nsqrt n)) 的 ，因为卡不到 (n^2) 。先把所有串丢进广义SAM，对每一个节点打标记，记录它最后一次被暴力跳到的串编号。如果已经相同就不跳了。对于每一个询问，沿着转移边走，走到终止节点的覆盖次数即为答案。 评测记录
CF427D Match & Catch
把两个串丢进广义SAM，各自维护endpos大小，大小为 (1) 那么答案与它的 (minlen) 取 (min) 评测记录
P4022 [CTSC2012]熟悉的文章
大家可以享受独自切CTS黑题的快感了，CTS黑题成为了一眼题（ 首先建SAM，每次询问的时候丢到转移边上跑，求出每一个询问串后缀和原串的最长公共后缀，做法同上面的LCS。显然二分答案。判断的时候，有个常用性质：设 (i) 处的匹配长度为 (ma[i]) ，那么 (i-ma[i]) 单调不降。然后就可以直接上单调队列优化了， (dp[i]=max{dp[j]+i-j } (i-ma[i]le jle i-L)) 。看不出单调性可以像我一开始的在单调队列里二分。。。评测记录
CF235C Cyclical Quest
首先倍长询问串丢到原串的SAM上跑。设当前匹配长度为 (now)，当 (nowge m) 时意味着产生了贡献。但是这并不意味着产生的贡献在这个节点，因为我们的串时被长的！所以要沿着后缀连接一直跳直到 (mxlen[u]le m) ，加上这个节点的状态数。而且，这么跳可能跳到重复的节点，那么还需要对每一个节点打标记。评测记录
P6640 [BJOI2020] 封印
和那道CTS水黑一样求出 (ma[i]) 表示到 (i) 的最大匹配长度。因为 (i-ma[i]) 单调不降所以可以二分。二分出 ([l,r]) 之间最靠左的 (i) 满足 (i-ma[i]+1ge l) ，那么 (ans=min(i-l,max_{ile jle r}{ma[j]}))。即在 (i) 右边的都可以完全匹配上， (i) 左边的不一定必然只能匹配一截，取最大的即可。那个 (max) 显然用个ST表维护一下。评测记录
P5576 [CmdOI2019]口头禅
正解是猫树分治？？反正我不会，但是 (O(nsqrt n)) 跑的飞起。先把所有串丢到广义SAM上，把询问挂到 (r) 上。对于每一个串暴力跳链，对于每一个节点维护当前连续覆盖它的串编号的左右端点。对于离线下来的询问按照 (l) 排序，对于跳到的节点直接二分到最大的 (l) 满足 ([l,r]) 被覆盖，最后求后缀最大值输出即可。然后command_clock说要把题出到树上卡掉这种做法，但是到现在还没出 评测记录
CF666E Forensic Examination
线段树合并维护endpos大小，把所有串丢到广义SAM上（包括最开始那个，只是不要操作线段树）。每次从 (S_r) 映射到 SAM 上的节点倍增往上跳到最低的满足 (mxlen[u]< r-l+1) 的节点 ，这时候 (S[l,...,r]) 一定被包括在这个状态里。然后我们查询这个节点对应的endpos在 ([l,r]) 内endpos大小的最大值以及下标即可。 评测记录
CF1037H Security
对 (S) 建SAM，把endpos集合先线段树合并维护出来，每一个询问串丢到转移边上跑。对于每一个位置我们可以用线段树求出 (T[1,...,i]) 是否在 (S[l,...,r]) 中出现，具体来说，(query(l+i-1,r)) 之内如果有节点 (u) 的endpos那么就是存在的。找到最靠后的那一个可以走严格大于 (T_i) 的转移边即可，之前的沿着 (T) 走。评测记录
P4094 [HEOI2016/TJOI2016]字符串
后缀自动机不擅长处理前缀 不然为啥不叫前缀自动机呢qwq 所以直接翻转整个串，于是就变成处理后缀的问题了。二分答案是显然的。考虑我们二分一个 (len) ，是否在 (S[a,...,b]) 内出现。这个可以先线段树合并维护endpos大小同时在后缀树上倍增，求出包含 (S[c-len+1,d]) 的节点，查询这个节点在 ([l+mid-1,r]) 内是否有endpos即可。评测记录
CF700E Cool Slogans
在后缀树上从上往下dp。对于每一个节点维护最靠下的能转移到它的节点，这个可以线段树合并维护endpos来求，即在 ([rev[u]-mxlen[u]+mxlen[tp],rev[u]-1]) 内至少出现一次。(rev[u]) 表示这个节点映射到序列上的位置。因为 (rev[u]) 必然存在，直接从二分的区间内去掉也是可以的。评测记录
P4770 [NOI2018]你的名字
发现这题的问题主要是 (sum mxlen[i]-mxlen[link[i]]) 会算重一些本身存在于 (S) 中的串。线段树合并维护(S) 的endpos，再对询问串 (T) 建SAM，求出每一个位置的最大匹配长度 (ma[i])。只不过这次要用线段树合并来判断这条转移边能不能走。设当前匹配长度为 (now) ，那么 ([l+now,r]) 内有endpos是能走这条转移边的充分必要条件。而在失配的过程中，我们只能每次将 (now) 减少一直到与 (mxlen[link[u]]) 相同再跳 (link) 而非直接跳。事可以用一个简单的均摊分析证明这个复杂度还是对的，即每次 (now) 只会增加 (1)，所以最多只会询问串长次。(ans=sum mxlen[i]-max(mxlen[link[i]],ma[maxendpos(i)])) ，maxendpos是这个节点最大的endpos。这样就能完成去重的工作了。评测记录
CF1276F Asterisk Substrings
略微思考可以发现字符串有 (...*,*...,*, ext{空串},s*t) 五种，前四种随便搞都可以，正串反串各建一个SAM，而第五种则是反串endpos为 (i+2) 的个数。如果对于每一个 (i) 都加上 (endpos=i+2) 的个数显然会算重。考虑丢到SAM上来计算这个贡献。同一个节点包括的字符串的贡献应该是相同的。考虑先求出反串SAM的dfs序，然后插到正串SAM的动态开点线段树里，注意插入的是dfs序，因为这样根据后缀自动机与后缀数组的联系，我们可以方便的去重，把一堆 (mxlen[x]+mxlen[y]-mxlen[operatorname{LCA}(x,y)]) 加起来即可。这样在线段树合并的时候还要维护区间dfs序最靠左最靠右的节点。我脑残复杂度算错写了倍增LCA。其实写ST表LCA可以 (O(nlog n)) 的 评测记录
P6292 区间本质不同子串个数
大型拉板子现场 先把询问都挂到 (r) 上。一个串右端点在 ([l,r-last-|S|+1]) 内就可以对答案产生 (1) 的贡献，(last) 是这个串最后出现的右端点。考虑从左往右扫到 (r) 并加入的本质是把 ([l,r]) 内的 (last) 全改成 (r) 。而这放到SAM上就是后缀树上的链覆盖，丢到LCT上，仿照树点涂色的写法access即可 仿照的意思是你还得写一颗线段树，插入完取区间求和即可。评测记录
P4482 [BJWC2018]Border 的四种求法
SAM的部分没多少，主要难点是DS。联系后缀数组可以发现我们要求的是最大的 (pin [l,r)) 使得 (p-l+1le lcs(i,r)=mxlen[operatorname{LCA}(to[i],to[r])]) 。SAM就用道这里，剩下会做的全是DS神仙。首先化式子， (i-mxlen[operatorname{LCA}(to[i],to[r])]<l) 。暴力从 (to[r]) 往上跳，线段树合并维护endpos，每次查询 ([l,min(r-1,l+mxlen[u]-1)]) 内是否有endpos即可据说这能过 。考虑如何把链缩掉，那只能重剖了。二次离线把询问挂到重链底端。然后仿照静态链分治的方法，沿重链往下跳，不动重儿子信息，每次统计三种贡献：子树内的；链上方轻子树的；链上方重儿子的。第一种直接线段树合并维护endpos查询。第二种再开线段树维护上面化的式子最小值。注意查询应该在线段树上二分，找到最右边的可行解。可以发现所有轻子树都被遍历了恰好一遍，加上线段树的 (log) ，总复杂度 (O(nlog^2 n))。评测记录
总结
- 暴力跳广义SAM的链是 (O(nsqrt n)) 的。
【注】我到现在只是看到一些金牌选手说是根号，但是到现在都没有看到过证明。某天Itst说他只会 (O(n^{1.67})) 的证明。所以我们只需要知道这东西能跑 2e5 的东西并且大部分情况卡不掉就是了（逃
upd:学校里讲课的时候被wh证明了就是 (nsqrt{n}) 。
设一个串长度为 (L)，那么覆盖 (L^2) 的路径长度；同时又有SAM一个节点最多被覆盖后缀树上儿子个数次，因此这个上限是 (|S|)（SAM大小）
那么每一次跳链是 (min(L^2,|S|)=Lmin(L,dfrac{|S|}{L})) 的，不超过 (sqrt{|S|}) 。
Orz万老爷！！！
-
(i-match[i]) 是单调不降的，(match[i]) 表示 (i) 点的最大匹配长度。
-
线段树合并可以方便地维护endpos
-
后缀树也是树，可以用LCT维护
整个人都自动机了！