后缀自动机SAM

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132560666

https://www.luogu.com.cn/problem/P3804

• fail：当前区间-1（最短串 去掉最前面 的字符）

• nxt：任意串 加上最后面

考虑新加入的字符为x，上一个为p，则 $nxt[p][x]=c$

当前的每个后缀如果本身nxt为空，都可以加x

代码：

然后考虑现在这样：

如果整个区间可以直接接x

则fail可以直接连过来：

就是这样子写：

但也有可能是这样：

我们考虑把其化为两个区间，另一个记为cq：

首先此时u的fail就可以连到cq了：

q的fail同理：

也就是：

然后考虑原先的大fail：

显然，连回q：

如果是本身连出去的：

同理

可得：

代码表示：

下一个处理nxt:

一样，变成了分别的nxt：

也就是：

另一个，本身连向此的nxt（这里 指的是p中的）：

就变到了cq：

也就是：

完整代码：