后缀自动机
题单介绍
# 后缀自动机
## 前置芝士
[后缀自动机1](https://etaoinwu.com/blog/感性理解-sam)
[后缀自动机2](https://oi-wiki.org/string/sam/)
[后缀自动机3](https://www.luogu.com.cn/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie)
[广义后缀自动机](https://www.cnblogs.com/Xing-Ling/p/12038349.html)
## 例题略解
#### [P3804 【模板】后缀自动机 (SAM)](https://www.luogu.com.cn/problem/P3804)
模板题，先按顺序把每一个压进去，然后按计数排序（就是SA里的那个）排一下序。
可以发现len的大小某种意义上就是该节点的深度，再用siz存一下，更新最大值就好了。
[$code$](https://www.luogu.com.cn/paste/jb3m72pn)
#### [P4070 [SDOI2016]生成魔咒](https://www.luogu.com.cn/problem/P4070)
为数不多的一看题面就有思路的紫题
***
**不开 $long long$见祖宗**
***
利用上述后缀自动机的树形结构。每个节点对应的子串数量是
$len_i-len_{fa(i)}$，对于每一个节点直接求和就ok。然后我们愉快的TLE/MLE $60pts$
显然，许多节点在之前已经计算过，可以直接转移，如果在添加时改变了fa的值直接重新加一下这个点就好了，用一下**map**存ch。
[$code$](https://www.luogu.com.cn/paste/g28ltm7d)
#### [P3975 [TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975)
和模板题有一定的联系还是先把每一个字符都压进去，
然后排序求出对应的siz值（每个字符在字串中出现的个数）。
在用一个sum数组记录一下子树及自身的siz和，对于T=0的情况直接把每个siz记录为1就好了，然后判断sum[1]与K的大小关系。
最后再递归输出就好了。
[$code$](https://www.luogu.com.cn/paste/32hrfavn)
#### [P6139 【模板】广义后缀自动机（广义 SAM）](https://www.luogu.com.cn/problem/P6139)
板子题，用的是离线做法，在线做法懒得学 ~~（其实是看不懂TAT）~~
思路比较好理解，无非就是把每个串压进字典树，然后bfs扫一遍加进SAM就好了。
* 注意：**开了long long见祖宗**
[$code$](https://www.luogu.com.cn/paste/quoo00d5)
#### [P3346 [ZJOI2015]诸神眷顾的幻想乡](https://www.luogu.com.cn/problem/P3346)
半个板子题，字串的数量把图里的每个点度为1的点向下扫一遍，放到字典树里，再跑一边广义后缀自动机就ok了。
* 注意：字典树从1开始tmp一定要初始化成1.
[$code$](https://www.luogu.com.cn/paste/j2riozpx)
#### [P5546 [POI2000]公共串](https://www.luogu.com.cn/problem/P5546)
#### [SP1811 LCS - Longest Common Substring](https://www.luogu.com.cn/problem/SP1811)
#### [SP1812 LCS2 - Longest Common Substring II](https://www.luogu.com.cn/problem/SP1812)
#### [SP10570 LONGCS - Longest Common Substring](https://www.luogu.com.cn/problem/SP10570)
其实这几个题都是一个题。。。（可能也就是第二个比较简单一点吧）
大概思路就是先读入一个串。然后将剩下的每一个分别和他比对，然后求出一个maxn数组，maxn[i]表示i结尾的最大的匹配长度。
因为是记录多个串，因此我们应该对于所有的取最小值，存到minn数组里，
如果i点可以被匹配那么他在parent树上的任意一点都可以被匹配到，可得到一下以下式子：
$\max(i)=\max\limits_{v\in son(u)}\{\min(mx(v),len(u))\}$
然后再每个串后更新minn，最后找minn最大值就好了。（逃
[$code1$](https://www.luogu.com.cn/paste/szscialp)
[$code2$](https://www.luogu.com.cn/paste/c1vg0u95)
[$code3$](https://www.luogu.com.cn/paste/t0qno752)
[$code4$](https://www.luogu.com.cn/paste/ryir9jbf)
#### [P4248 [AHOI2013]差异](https://www.luogu.com.cn/problem/P4248)
题目中的式子就是所有后缀两两除公共前缀外的长度。
还是先初始化，然后计数排序求一下siz数组（siz[i]表示以i节点开头的不同字串的数量）
* 递推式子：
$\sum\limits_{i=tot,now=A[i]}^{1}tre[now].len-tre[tre[now].fa].len)*siz[now]*(n-siz[now]) $
前半部分就是求不同字串的个数（长度），后面就是排列组合，
以i开头的有siz[i]个，和剩下的n-siz[i]个的组合数显然就是$siz[now]*(n-siz[now])$
* 注意：理论上来讲本题应该反着建后缀自动机，将前缀化为后缀，但是观察题面不难发现求前缀和后缀是差不多的。。。
[$code$](https://www.luogu.com.cn/paste/rcd8ayss)
#### [P1368 【模板】最小表示法/工艺](https://www.luogu.com.cn/problem/P1368)
本来应该是一个最小表示法的题，但是拿SAM也能做 ~~（主要是懒得学）~~。
SAM的话就是最小循环移位的板子题了，先把环化串，把串插进去两次。然后就对于每一层取最小的字典序的就可以了，共取n层。
[$code$](https://www.luogu.com.cn/paste/l513xagr)
#### [P2178 [NOI2015] 品酒大会](https://www.luogu.com.cn/problem/P2178)
我真傻，真的，我单知道要反转字符串，却把反转打在了读入前面TAT
先是对于这个串建后缀自动机（建的时候要存一下这个节点在原来字符串中的位置），然后求出siz，siz大于1时把now与fa[now]差分存一下$\frac {(siz[now]-1)\times siz[now]}2$，也就是$C_{siz[i]}^{2}$算出r相似的总数，顺便再更新一下配酒之后的美味度（好像是叫这个名字）。
最后再用前缀和把差分给搞回去，美味度依次求最值就好了
* 注意：要把最大与次大，最小与次小分别相乘比较（之前SA里面好像也说过）
[$code$](https://www.luogu.com.cn/paste/yuajuwlm)
#### [P4022 [CTSC2012]熟悉的文章](https://www.luogu.com.cn/problem/P4022)
**SAM+二分答案+单调队列优化dp**
~~乍一看，这题挺花里胡哨，再定睛一看，就是挺花里胡哨。~~
和前面的那个[公共串](https://www.luogu.com.cn/problem/P5546)有一点相似，先把文本串压 SAM （建不建 Tire 都差不多）然后对于每一个进行一下匹配。
以 num[i] 表示以第 i 个结尾的与文本串的最长公共字串的长度。
以 f[i] 表示前i个字符的字串中可以匹配的最长的长度，可以得到以下式子：
$f[i]=\max (f[i-1],f[j]+i-j)$
满足条件：$(i-j \ge L)$ 并且 $s[j+1..i]$ 能够匹配.
显然，可以采用单调队列来优化
```cpp
while(head<=tail&&f[q[tail]]-q[tail]<=f[i-mid]-(i-mid))
tail--;
```
根据式子，把不优于现在的解的给提出队列，
```cpp
while(head<=tail&&q[head]<i-num[i])
head++;
```
把超出范围的给干掉。
如果队列还有数的话，更新就好了。
[$code$](https://www.luogu.com.cn/paste/voa0j94r)
#### [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770)
[参考题解](https://www.luogu.com.cn/blog/_post/100268),懒得写了 ~~（其实是不太会）~~
[$code$](https://www.luogu.com.cn/paste/9dte6ksm)
码完之后试着改了一下码风，自我感觉良好，[这里](https://www.luogu.com.cn/paste/opp74h1l)