后缀自动机

如你所见，后缀自动机。

然而就nm看不懂，先看不懂它的图是啥，又看不懂它的边是啥，现在还是看不懂它的边是咋找出来的。可是咱不想搞不清楚它是干嘛的就直接用啊靠。

后缀自动机首先是自动机。一个字符串S的后缀自动机能接受S的所有后缀。基于它的这个性质，它能够做到：

• 查询子串是否出现：这显然跑一次，能在自动机上跑完就是出现过。
• 统计不同子串的数量：自动机上每条不同的路径对应一个不同的子串。定义$d(x)$为以x为起点的路径数目，递推即可。
• 计算所有不同子串的长度总和：得到上面的$d$。以x为起点，每条路径都会让子串总长度增加路径个。依然是递推。
• 字典序第k小子串：当你有路径数了，只需要按照字典序对节点排序，然后像编码一样找。
• 最小循环移位：指将原字符串首尾相接移位，找到字典序最小的一个。将字符串$S$断环成链$SS$，然后建立SAM，贪心找最小直到长度达到$|S|$即可。
• 多组子串出现次数：dfs预处理每个节点的终点集合大小。在自动机上查找串$P$对应的节点,存在则答案为该节点的终点集合大小；不存在答案为$0$.
• 所有出现位置：遍历树，一旦发现终点直接输出。

建立

最暴力的方式是建立一个O(n^2)级别的自动机，不过那个复杂度就没什么意义了。后缀自动机需要满足状态数最少，为线性级别，且转移（边）也为线性级别。

然后，我们可以开始折腾了。

定义串S的$endpos(x)$为一个集合，元素为x在其内出现的所有位置的结尾下标。

资料

• 参考资料
• 2015年国家集训队论文

子串第一次出现的位置

对SAM中所有状态预处理firstpos（第一次出现该状态的末端位置，也就是endpos集合的最小元素）。

扩展源函数为sam_extend()。创建新状态cur时，令

$firstpos(cur)=len(cur)-1$

当q复制到clone时，令

$firstpos(clone)=firstpos(q)$

需要的答案就是$firstpos(t)-|P|+1$，$t$为字符串$P$的状态。每次查询需要$O(|P|)$

最短未出现字符串

动态规划。

让$d_v$为节点$v$的答案。如果不存在使用字符集中至少一个字符的转移，那么$d_v=1$，否则

$d_v=1+\min_{w:(v,w,c) \in SAM} d_w$

字符串可以由转移推回去。