后缀数组 & 后缀自动机
后缀数组（SA）
定义
给定一个字符串 $S{1 \dots n}$，你需要对这个字符串的 $n$ 个后缀按照字典序排序，排序后的下标数组就是 $sa_i$，也即后缀数组 Suffix-Array，每个后缀在 $sa$ 中的排名就是 $rk_i$，容易发现 $sa_{rk_i}=i,rk_{sa_i}=i$。
构建方法
首先，我们可以暴力排序，排序的时间复杂度是 $O(n \log n)$，每次字符串比较为 $O(\log n) \sim O(n)$ 的，总时间复杂度为 $O(n \log^2 n) \sim O(n^2 \log n)$。
这里引出一种基于倍增的 $O(n \log n)$ 解法。
首先我们考虑将长度为 $1$ 的字符串进行排序，得到每个后缀取长度为 $\min(len,1)$ 的前缀的 $rk$ 和 $sa$ 数组，容易发现，此时 $rk$ 可能有重复。
然后我们将长度为 $1$ 的字符串和长度为 $2$ 的字符串拼在一起排序，得到每个后缀取长度为 $\min(len,1+2=3)$ 的前缀的 $rk$ 和 $sa$ 数组。
直到 $rk$ 中的数字都不重复即可。
因为 $2^0 + 2^1 +\dots +2^{\log_2 n} \ge n$，所以此过程最多执行 $O(\log n)$ 次，每次因为 $rk$ 的值域不大于 $n$，因此我们可以使用基数排序做到 $O(n \log n)$。
具体的过程参见下图，图片来源于 OI-wiki：
代码如下所示，里面有很多卡常的技巧：
1 |
|
height 数组
定义 $s_i$ 为以 $i$ 号元素为开头的后缀，并且定义 $h_i$ 为 $\operatorname{lcp}(s_{sa_i},s_{sa_{i-1}})$，则 $h_1=0$。
如何快速获取 $h$ 数组的值呢？
- 引理：$h_{rk_i} \ge h_{rk_{i-1}}+1$。
据此，我们可以 $O(n)$ 暴力求出 $h$ 的值。
1 | for(i=1;i<=n;i++){ |
应用
最小表示法
直接将字符串 $S$ 拼接两份变成 $SS$ 即可，然后就是模板后缀排序了。
两个后缀的最长公共前缀
$\operatorname{lcp}(sa_i,sa_j) = \min_{k=i+1}^j h_k$。
可以感性理解一下，按照后缀排序之后，一个字符变动之后就不会再变回来了，这种情况也可以扩展到两个子串的最长公共前缀。
本质不同子串的数量
子串就是后缀的前缀，所以可以枚举每个后缀，计算前缀总数，再减掉重复。
相邻两个后缀重复的部分就是 $h_i$，并且因为我们是按照后缀排了序，所以这样减去之后不会再有重复。
所以 $sum= \dfrac {n(n-1)}{2}-\sum_{i=2}^n h_i$。
出现至少 k 次的子串的最大长度
根据 $h$ 数组的定义，任取 $h$ 数组中连续的 $k-1$ 段就是一个答案，然后对所有答案取一个 $\max$ 即可。
是否有某字符串在文本串中至少不重叠地出现了两次
将 $h$ 按照大小为 $|s|$ 分成若干段，每段可以用 RMQ 获得最长的后缀和最短的后缀长度，然后判断这两个长度之差是否大于等于 $|s|$ 即可。
连续的若干个相同子串
设 $s_i$ 为以 $i$ 开始的后缀，$p_i$ 为以 $i$ 结束的前缀，以两个相同子串为例：
首先枚举长度 $|s|$，如果有连续的若干个相同子串的长度等于 $|s|$，那么其一定跨过所有 $s_i(i \bmod |s|=0)$，于是设 $j$ 是枚举的长度，我们可以求出 $s_i$ 与 $s_{i+j}$ 的最长公共前缀 $a$ 和 $p_{i-1}$ 与 $p_{i+j-1}$ 的最长公共后缀 $b$，如果 $a+b <j$，则在 $[i,i+j)$ 内没有这个子串第一次出现的落点，否则有 $a+b-j+1$ 个连续的落点可以。
统计连续落点的答案就可以了，如下图：
结合数据结构
例如并查集、线段树、单调队列等，因为 $h$ 数组有较好的性质，所以一些区间上的问题都会涉及到。
例如：#2064. 「HAOI2016」找相同字符 - 题目 - LibreOJ (loj.ac)，#2377. 「AHOI2013」差异 - 题目 - LibreOJ (loj.ac) 等。
如果是多串匹配，需要用到 SAM（后缀自动机），但是我们可以用 $O(mn\log n)$ 暴力解决此问题。
后缀平衡树
定义
后缀平衡树的每个节点代表了某字符串的一个后缀，特别的，后缀平衡树的中序遍历就是后缀数组 $sa$。
除此之外，后缀平衡树还支持在字符串前面插入一个字符动态维护后缀数组 $sa$，同时也支持删除一个字符。
构建
构建可以直接看做挨个插入 $n$ 个字符，首先如果插入一个字符，把它与根节点所代表的后缀比大小，如果第一个字符就能区分胜负，就按照大于小于的关系往左边或者右边走。
如果不能，则去掉第一个字符，剩下的两个字符串一定都在这个后缀平衡树里面，考虑如何 $O(1)$ 比大小。
后缀平衡树的每个节点维护一个值 $val$，满足中序遍历的 $val$ 递增，我们可以每个节点设置一个区间 $(l,r)$，它的 $val$ 就是 $\frac {l+r}{2}$，它的子节点的区间就分别是 $(l,val),(val,r)$，这么递归下去就可以 $O(1)$ 比较大小了。
因此总的时间复杂度是 $O(n \log n)$。
特别的，平衡树要使用好维护的类型，比如替罪羊树，删除和插入都是均摊 $O( \log n)$ 的，如果子树不平衡，特别注意需要拿出来重构。
树上后缀排序
类比于后缀数组，第 $i$ 个节点代表的字符串是它到根节点路径上的字符连接起来的字符串，我们要维护这个字典序，也可以按照上面的后缀平衡树来处理。
核心思想就是：
- 插入一个字符，先比较它。
- 如果比较失败，则剩下两个字符串一定在平衡树中出现过，即可 $O(1)$ 比较。
所以靠这样，我们总的时间复杂度是 $O(n \log n)$，空间复杂度为 $O(n)$ 解决了树上后缀排序的问题。
这里放一下后缀平衡树的代码：P6164 【模板】后缀平衡树
1 |
|
后缀自动机（SAM）
定义
这个自动机由节点和转移边构成，接受且仅接受一个字符串 $S$ 的所有子串。
例如 $S=\texttt{abbb}$，其构建的后缀自动机如下：
容易发现，这个自动机也可以等价于接受且仅接受字符串 $S$ 的所有后缀，故称为后缀自动机。
构建
我们考虑增量式构建，即在构建完 $S[1,i-1]$ 的后缀自动机后，添加一个字符 $i$，尝试构造 $s[1,i]$ 的后缀自动机。
为了以后构造的时间复杂度保证，这里引入一个概念 $\text{endpos}$。
终止集合
一个 $S$ 的子串 $T$ 在 $S$ 中可能出现过很多次，例如 $S=\texttt{abaab},T=\texttt{ab}$，那么 $T$ 在 $S$ 中出现了 $2$ 次，定义其 $\text{endpos}$ 集合为出现的所有结尾的位置的集合，在这个例子中 $T$ 的 $\text{endpos}$ 集合就是 $2,5$。
在后缀自动机上走到一个点可能有多种不同的路径，定义这个点所代表的字符串集合就是这些所有路径所构成的字符串集合，例如上文中最右边的绿色节点的字符串集合就是 $\texttt{abbb}$ 和 $\texttt{bbb}$。
字符串构建出来的满足要求的后缀自动机可能有多个，我们这里只讨论一种简单的构建方式，并且能够保证这个方法构造出来的后缀自动机满足其定义。
我们此处构造出来的后缀自动机的每个节点代表的字符串集合，设最长的一个为 $S$，最短的一个长度为 $T$，那么 $T$ 一定是 $S$ 的后缀，并且这个字符串集合仅包含 $S$ 的所有后缀（包括自己）中长度大于等于 $|T|$ 的。
例如 $S=\texttt{ababb},T=\texttt{abb}$，那么这个节点包含 $\texttt{ababb},\texttt{babb},\texttt{abb}$，并且这个节点的所有字符串的 $\text{endpos}$ 集合完全相同，并且所有 $\text{endpos}$ 集合完全相同的字符串一定在一个节点内，我们称这些字符串为一个等价类。容易发现当我们构造了 $S[1,0]$ 的时候满足条件，我们接下来通过后缀链接来使得加进每一个字符之后这个后缀自动机都满足这个条件。
后缀链接
对于 $pos$，定义它的后缀链接为 $fail_{pos}$，其代表的字符串的最长的长度为 $len_{pos}$，其代表的字符串最短的长度为 $lenm_{pos}$，满足 $len_{fail_{pos}}=lenm_{pos}-1$。
当 $pos$ 代表的字符串为空时，它没有后缀链接。容易发现，这些后缀链接构成了一个以空字符串代表节点为根的树。
注意：我们不需要再额外记录 $lenm_{pos}$，它可以通过父亲的信息得到。
增量构造
设 $S[1,i-1]$ 所在的节点为 $p$，那么新增字符 $S[i]$ 之后，必定会出现一个新的等价类包含 $S[1,i]$，所以新建一个节点 $now$ 表示这个新的包含 $S[1,i]$ 的等价类，我们现在知道 $len_{now}$ 了，接下来就是更新后缀自动机和后缀链接。
首先，如果 $p$ 在后缀自动机上没有字符为 $S[i]$ 的出边，那么新建一条指向 $now$，然后令 $p \gets fail_p$。
如果一直到根都没有，那么 $fail_{now}$ 显然等于 $root$，否则设 $p$ 在后缀自动机上字符为 $S[i]$ 的出边指向 $q$。（这里的 $p$ 只取深度最深的一个节点，因为深度浅的没什么大用，因为肯定不会成为 $now$ 的 $fail$ 并且后缀自动机的形态也不会发生变化）
然后我们发现 $q$ 所代表的字符串中，只有一个的 $\text{endpos}$ 集合会发生更改，就是最短的那个字符串，因此，如果 $len_p+1=len_q$，那么 $q$ 所有东西都不变，然后令 $fail_{now}=q$ 即可。
如果 $len_p+1 \ne len_q$，那么我们需要把 $len_p+1$ 的字符串从 $q$ 里面分裂出来，于是新建一个节点 $temp$，$len_{temp}=len_{p}+1$，并且我们可以发现 $temp$ 和 $q$ 在后缀自动机上的出边根据定义应该完全相同，因此这一部分复制即可。
根据 $fail$ 的定义，$fail_q=fail_{now}=temp$，于是就完成了构造，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$（字符集大小为常数），证明详见 OI-wiki。
下面给一个构建的伪代码：
1 | now=1,tot=1,root=1; |
后缀树
后缀树就是把一个字符串 $S$ 的所有后缀放到 Trie 上面形成的树。
但是这样的话节点数量是 $O(n^2)$ 的，因此我们构建出来反串的后缀自动机的 fail 树，然后一条边代表多个字符即可。
因为后缀树一般不常用，此处就不展开讲了。
应用以及性质
- 不同子串的数量：显然，所有节点的 $len_x-len_{fail_x}$ 的和。
- 检查字符串是否出现：直接放到后缀自动机上跑，如果跑不了了就没有出现过。
- 检查字符串出现的次数：首先预处理每个节点 $\text{endpos}$ 的大小，这个可以在每个前缀所代表的节点地方打个标记，然后每个节点 $\text{endpos}$ 的大小就是子树标记数量（我们也可以用线段树合并得到集合），然后找到询问字符串代表的节点，输出标记数量即可。
- 检查字符串出现的位置：同上，记录最大或者最小即可，有的时候可以用线段树合并维护整个集合。
- 最短的没有出现的字符串：后缀自动机上 DP 即可，DP 很简单，此处略。
- 多个字符串间的最长公共子串：首先选取最短的串构建 SAM，然后剩下的串在这个 SAM 上跑，如果有转移边就转移，否则跳 fail 直到有转移边为止，最后在每个节点更新一下其所代表的字符串中最长的公共子串即可，因为长度每次最多加 $1$，所以时间复杂度为 $O(\sum |S|)$。
- 字典序第 $k$ 大，循环移位等建议使用后缀数组完成。
例题
一个字符串，每次给字符串末尾添加一个字符，或者询问这个字符串第 $l$ 到第 $r$ 个字符有多少个本质不同的子串，强制在线，时间复杂度要求小于等于 $O(n \log^2 n)$。
解法如下
首先我们考虑求出点对 $(p,q,a,b)$ 的具体值（$1 \le p \le q \le |S|,a \ge b,p-a+1 \ge 1$），这些点对代表：
对于所有 $S[q-a+1 \sim q-b+1,q]$，其上一个出现的位置一定是 $S[p-a+1 \sim p-b+1,p]$，这个点对可能有 $O(n^2)$ 个，但是我们接下来证明，这个点对可以缩减为 $O(n \log n)$ 个。
考虑每次构建的过程，如果我们在整个串的 $fail$ 树上，每个节点记录其当前 $\text{endpos}$ 是什么，然后枚举 $i$ 找到 $S[1,i]$ 代表的节点，并且这个节点以及其祖先都可以得到一个点对 $(p,q,a,b)$，$p$ 就是加入之前的 $\text{endpos}$，$q$ 就是 $i$，$b$ 是当前节点代表的字符串中长度最小的字符串的长度，$a$ 就是当前节点的 $len$，并且让这条链上的所有节点的 $\text{endpos}$ 都变成 $i$。
这样做是 $O(n)$ 的，但是我们可以证明相同的 $p$ 在这条链上一定是一个连续段并且 $(a,b)$ 也连续，所以我们可以像 LCT 那样使用 access 来执行操作。
根据 LCT 的 access 操作的时间复杂度，这样的四元组只有 $O(n \log n)$ 个，结论证毕。
这道题中，如果要支持动态加最后一个字符，只需要处理我们复制节点的时候，$fail$ 的更改即可，这个不难处理，处理好 pushup 的顺序即可。然后 LCT 的时候，我们需要记录当前 Splay 的 $p$ 是多少，这个显然是当前 Splay 中 $len$ 最长的节点的 $len$，然后 $b$ 就是这条链链顶父亲的 $len+1$，$a$ 就是当前节点的 $len$，$q$ 就是 $i$。
最后得到了 $(p,q,a,b)$ 的四元组，我们可以用它们来做很多事情，因题而异。这道题中，我们维护主席树，即为当询问的 $r \ge q$ 的时候，这个时候我们对于 $b \le i \le a$ 讨论一下，发现 $l \le p-i+1$ 的时候这个字符串的贡献已经处理了，所以我们需要让 $p-i+1<l \le q-i+1$ 的 $l$ 点加上 $1$，然后我们把它转化为差分+前缀查询，就变成了让 $p-i+2$ 位置 $+1$，让 $q-i+2$ 位置 $-1$，然后考虑 $[b,a]$，问题转化为了让 $p-a+2 \sim p-b+2$ 位置 $+1$，$q-a+2 \sim q-b+2$ 位置 $-1$，这个可以用主席树轻松维护。
最后就是需要注意一下 $p=0$ 的情况，这个情况更好处理，此处不再赘述。
下面给一个非强制在线版的提交记录：代码 here。
SAM 1 题面
给出一个字符串 $S$，定义函数 $f(l,r)$ 为 $S[l,r]$ 的每个后缀与 $S[l,r]$ 的 LCP 之和。现在询问 $q$ 次，每次给出 $l,r$，请输出 $f(l,r)$，非强制在线。
数据范围：$|S|,q \le 2 \times 10^5$，时间复杂度要求低于 $O(n \sqrt{n})$。
SAM 1 题解
把整个串反过来，题目就变成了求 $\sum_{x=l}^r \min(x-l+1,len)$，$len$ 表示以 $x$ 为结尾的前缀和 $s[l,r]$ 的 LCS。
首先建立这个字符串的 fail 树，找到 $s[l,r]$ 在 fail 树上的节点，这个部分可以倍增单 $\log$ 解决，同时我们需要处理每个前缀 $[1,i]$ 在 fail 树上的节点编号，这个标记一下就可以了。
那么 $len$ 实际上就是 $[1,x]$ 在 fail 树上的节点和 $[l,r]$ 在 fail 树上的节点的 LCA 的 $len$ 值。
我们首先不管 $x$ 的上下界，那么就要求 $\sum_{x=1}^n \min(x-l+1,len)$，这个我们可以先将 fail 树重链剖分一下，然后我们考虑下面这一种剖分方式（先不管轻重儿子，以图片为准，方框是重链）：
如果 $[l,r]$ 代表的节点是 $5$ 号节点，那么首先我们需要加上 $5$ 号节点子树内部对答案的贡献，然后跳到 $6$ 号节点，加上 $6$ 号节点子树内部对答案的贡献，但是这个时候我们发现 $5$ 号节点子树内部对答案的贡献算重复了，所以要减去 $5$ 号节点子树内部对答案的贡献（这里有一些细节留给读者思考）。再跳到 $2$ 号节点，加上 $1$ 号节点本身以及他附属轻子树中所有节点对答案的贡献，然后加上 $2$ 号节点子树对答案的贡献，减去 $6$ 号节点子树对答案的贡献。
首先子树内部我们可以预处理子树的 endpos 集合（线段树合并），然后对于所有询问一起处理就可以了，因为 $len$ 确定，所以上面的 $\min(x-l+1,len)$ 变成 $\min(x,len+l-1)-l+1$，然后发现 $\min$ 具有单调性，于是用线段树维护区间信息就可以轻松完成，这一部分甚至可以强制令贡献的 $x$ 在 $[l,r]$ 区间内。
然后考虑链上的贡献，轻儿子子树可以暴力遍历，就会得到一部分点对 $x,len$，然后令 $\min(x-l+1,len)$ 变成 $\min(x-len,l-1)-l+1+len$，注意到这个也具有单调性，所以我们可以直接处理 $1 \le x \le n$ 的答案，考虑减去 $1 \le x < l$ 和 $r<x \le n$ 的答案。
当 $1 \le x < l$ 的时候上式一定等于 $x-l+1$，因为 $len \ge 0,x-l+1 \le 0$，这个统计多出来的贡献是简单的。
当 $r<x \le n$ 的时候上式一定等于 $len$，因为 $len \le r-l+1,x-l+1 \ge r-l+1$，这个统计也是简单的。
因此我们这道题就在 $O(n \log^2 n)$ 的时间复杂度内解决了。
同理，这个方法可以适用于 P4482 Border 的四种求法，只不过是把求和符号换了一下，然后强制要求 $x-l+1 \le len$ 求最大的 $x-l+1$，某种意义上来说其实更为简单。
总的来说，时间复杂度为大常数 $O(n \log^2 n)$，差点就 TLE 了。
SAM 2 题面
给定一个字符串 $S$ 和一个权值数组 $w$，设函数 $f(l,r)$ 表示用 $S[l,r]$ 构建 KMP 前缀 fail 树，其中 $S[l,i]$ 在树上的深度是 $dep_i$，空节点在树上的深度是 $0$，$f(l,r)=\sum_{i=l}^r dep_iw_i$，询问 $q$ 次，每次输出 $f(l,r)$，非强制在线。
数据范围：$|S|,q \le 2 \times 10^5$，时间复杂度要求低于 $O(n \sqrt{n})$。
SAM 2 题解
考虑分块求解，首先根据 KMP 的 fail 树的定义把题目要求 $f(l,r)$ 转化为求出 $S[l,r]$ 的每个前缀在 $S[l,r]$ 中所有出现位置的结束位置的 $w$ 之和。
设块长为 $B$，当 $r-l \le 2B$ 的时候可以暴力 KMP 处理。
否则我们首先设 $l$ 右边第一个块的左端点为 $x$，那么我们考虑处理 $S[l,r]$ 长度小于等于 $x-l$ 的前缀所贡献的答案，如果它们的 endpos 在 $S[l,x-1]$ 内，这个可以直接在 $S[l,x-1]$ 上 KMP 暴力处理，然后它们的 endpos 就只能在 $S[x,r]$ 内，于是我们可以用后缀和优化，用 endpos 在 $S[x,n]$ 的答案减去 $S[r+1,n]$ 的答案，这个并不困难，用 dfs 序维护即可。注意此处不能使用树状数组支持链加单点查询，需要使用 $O(\sqrt{n})-O(1)$ 的分块来支持链加单点查询平衡时间复杂度。
最后就是处理 $S[l,r]$ 中前缀长度大于 $x-l$ 对答案造成的贡献了，容易发现，这些贡献一定是形如下面这个样子：
也就是如果蓝色的是满足题目条件的一个字符串，那么容易发现 $S[X,M]=S[P,N]$，即 $S[X,R]$ 的答案一定包含 $S[L,R]$ 中前缀长度大于 $X-L$ 的答案，于是我们先让 $S[L,R]$ 的答案加上 $S[X,R]$ 的答案，再考虑减去不合法的答案。这一部分可以处理出 KMP 用前缀和统计答案。
什么情况不合法呢？即为上面的 $\operatorname{lcs}(X-1,P-1) < X-L$ 就不合法了，那么当 $P$ 固定且假设它合法的时候计算多的答案就是 $ w_{P}+w_{P+1}+w_{P+2}+\dots+w_{\min(P+\operatorname{lcp}(P,X)-1,R)} $。
其中 $\operatorname{lcp}(P,X)$ 可以预处理 Z 函数算出来是多少，然后我们要统计的答案就是 $ \sum_{P=X,\operatorname{lcs}(X-1,P-1) < X-L }^R (w_{P}+w_{P+1}+w_{P+2}+\dots+w_{\min(P+\operatorname{lcp}(P,X)-1,R)}) $。
把 $w$ 做一个前缀和就是 $ \sum_{P=X,\operatorname{lcs}(X-1,P-1) < X-L}^R (w_{\min(P+\operatorname{lcp}(P,X)-1,R)}-w_{P-1}) $。
于是我们对同一个 $X$ 的所有询问按照 $R$ 双指针即可，然后因为 $X-L \le \sqrt{n}$，前面的可以暴力枚举前缀算，后面的 $\min(P+\operatorname{lcp}(P,X)-1,R)$ 需要打一个标记，再在标记处修改一下答案就可以了。
总的时间复杂度是 $O(n \sqrt{n})$，有的时候需要卡一下常数才能通过，特别注意的是递归是不能有太多次的。
SAM 3 题面
给定一个串 $S$，再给 $n$ 个模式串 $S[l_i,r_i]$，还有 $q$ 次询问所有模式串在 $S[a_i,b_i]$ 中出现了多少次。
数据范围：$|S| \le 4 \times 10^5,n \le 10^6,q \le 10^5$，时间复杂度要求小于等于 $O(|S| \log^2 |S|)$。
SAM 3 题解
考虑基本子串结构，于是问题就变成了平面上 $S[a_i,b_i]$ 右下角出现了多少次模式串。
接下来容斥，首先答案需要加上 $S[a_i,b_i]$ 这个等价类中右下角出现了多少次字符串，这个用二维数点即可解决，因为同一个等价类形态完全相同，所以找最左下角的代表元即可。
然后我们发现答案还需要加上 $S[a_i,b_i]$ 这个等价类下面出现的字符串的次数，根据基本子串结构的性质，就是在反串 Parent 树上这个等价类的后缀的所有节点祖先所包含的模式串的数量，这个因为等价类周长之和为 $O(n)$ 所以可以预处理，然后 $O(1)$ 查询。
答案还有等价类右边的出现的模式串的次数，这一部分我们需要用到容斥，如下图所示：
相当于加上右面绿色的所有答案，容易发现右面的一定是一个等价类的代表元的子串，现在我们处理出来每个代表元的答案就可以了，这个比较好处理，一个代表元所在等价类右边相邻一定只有一个上边界对齐的等价类，于是我们依照这个建立出来拓扑关系，然后递推处理即可，同时需要记得加上等价类下面所有部分的答案。
最后要减去绿色区域不在红框之内的方案数，容易发现这是等价类的一个前缀所代表的节点在正串 Parent 树上的祖先的答案，于是直接像蓝色部分一样维护前缀和就可以了。
总的时间复杂度为 $O(n \log n)$，但是常数较大，实现不好还跑不过 $O(n \log^2 n)$ 的。
SAM 4 题面
给定 $n$ 个模式串 $S_i$ 和一个文本串 $T$，还有 $m$ 次询问所有模式串在 $T[a_i,b_i]$ 中出现了多少次。
数据范围：$|T| \le 5 \times 10^5,1 \le n,m \le 5 \times 10^5,\sum |S| \le 10^6$，时间复杂度要求小于等于 $O(|S| \log |S|+|T| \log |T|)$。
SAM 4 题解
首先把这 $n$ 个模式串放到 AC 自动机上建立出来一棵成型的 fail 树，然后考虑计算 $T[a_i,b_i]$ 的贡献。
我们需要处理出在 $T_i$ 结尾的模式串的最长的一个，那么代表 $T[j,i]$ 是相同后缀中最长的一个能够和模式串匹配的。得到了这个东西之后，我们可以预先处理出来 $T[a_i,b_i]$ 中最靠后的 $T[j,i]$ 并且满足 $a_i \le i \le b_i,j<a_i$，找到这个答案之后，容易发现，所有 $i<k \le b_i$ 结尾的模式串左端点一定都不会超过 $a_i$，因此这一部分可以直接计算。
然后就是找到的 $T[j,i]$，那么这个时候问题就变成了求出来这个字符串的某一个后缀出现了多少次模式串，这个也是非常好预处理的，所以这道题就做完了。
时间复杂度是 $O(|T| \log |T|)$ 和小常数，时间是能够通过的。
SAM 5 题面
给定两个字符串 $S_1$ 和 $S_2$，多次询问字符串 $S_1[L,R]$ 的所有子串的长度乘上它在 $S_2$ 中出现的次数的最大值。
如果长度和询问同阶，要求时间复杂度小于等于 $O(n \sqrt{n})$，$n \le 10^5$。
SAM 5 题解
考虑一下先分块，设 $L$ 右边第一个块的左端点为 $X$，那么 $S_1[X,R]$ 的答案可以直接双指针计算，$S_1[L,X-1]$ 的答案也可以直接暴力计算，然后接下来需要计算左端点在 $[L,X-1]$ 右端点在 $[X,R]$ 的答案。
这样的话询问可以拆分成 $n\sqrt{n}$ 个，每个形如 $[l,r]$ 表示左端点为 $l$，右端点不能超过 $r$ 的在 $S_2$ 中的权值的最大值。这样的话，我们可以直接用反串的 Parent 树来处理左端点固定的时候的答案，这样的话就可以直接在 SAM 上得到这 $n\sqrt{n}$ 个节点就可以了。
然后 $O(n)$ 遍历计算即可，时间复杂度是 $O(n \sqrt{n})$。
SAM 6 题解
待补。