SAM 练习题

两个技巧：

• SAM 匹配，删除最前面字符

• 后缀树路径上，字符串长度连续

• 一个区间的子串可以倍增得到

线段树合并维护 \(\text{endpos}\)

SP687

link

考虑周期转 Border，一个存在的 Border 为 \(\text{lcp}(i,j)\)，对应周期为 \(|i-j|\)，周期出现整次数为 \(\dfrac{|i-j|}{\text{lcp}(i,j)}\)。线段树合并求出每个子串的 \(\text{endpos}\)，然后求相邻位置之间距离的最小值。

Luogu4094 [HEOI2016/TJOI2016] 字符串

link

二分长度，相当于求一个子串是否在另一个子串内出现过。

线段树合并求出 \(\text{endpos}\)，只需要判断一段区间是否有值。

Luogu4384 制胡窜

link

先线段树合并，求出 \(\text{endpos}\)。

考虑我们选两个位置，相当于用两个长度为 \(len-1\) 的区间覆盖所有 \(\text{endpos}\) 位置，我们要求这个方案数。

如果覆盖不了所有点，无解。

否则分讨：

• 所有点可以被一个区间覆盖

那么我们枚举第一个区间覆盖了多少个点，设为 \(i-1\)，贡献为 \((p_i-p_{i-1})(len-(p_k-p_i))=(len-p_k)(p_i-p_{i-1})+p_i(p_i-p_{i-1})\)。

边界特判，两边贡献分别为 \((p_1-len-1)(len-(p_k-p_1)),\sum\limits_{j=p_k-len+1}^{p_1} (n+1-j)\)，后者是等差数列求和。

• 所有点不可以被一个区间覆盖

设左边能覆盖到 \(L\) 个点，右边 \(R\) 个点。

当 \(L<R\) 时：方案数为 \((len-(p_L-p_1))(len-(p_k-p_R))\)。

当 \(L\ge R\) 时：

枚举第一个区间覆盖到的位置 \(i-1\)，贡献为 \((p_i-p_{i-1})(len-(p_k-p_i))=(len-p_k)(p_i-p_{i-1})+p_i(p_i-p_{i-1})\)。

边界特判，右边卡极限为 \((p_R-p_{R-1})(len-(p_k-p_R))\)，左边卡极限为 \((len-(p_L-p_1))(len-(p_k-p_{L+1}))\)。

维护 \(\sum (p_i-p_{i-1}),\sum p_i(p_i-p_{i-1})\) 即可。

SAM 上跑匹配

Luogu4022 [CTSC2012] 熟悉的文章

link

二分，我们只要求零散字符数量的最小值。

考虑 dp，设 \(f[i]\) 为以 \(i\) 结尾的答案。

考虑匹配，求出每个位置结尾的最长公共子串，设子串开头为 \(p_i\)。

那么 \(f[i]=\min_{j=p_i-1}^{i-mid} \{f[j]+1\}\)。

使用单调队列，时间复杂度 \(O(n\log n)\)。

Luogu4770 [NOI2018] 你的名字

link

枚举 \(T\) 的子串的结尾位置 \(i\)，我们当前要算的子串开头位置是一段前缀，考虑求出这个前缀位置。

算的子串不能重复，所以对 \(T\) 建立 SAM，可以通过插入的点得知与 \(T\) 不重复的前缀位置。

还有 \(S\) 的限制，我们考虑在 \(S\) 的 SAM 上跑匹配，求出 \(i\) 位置结尾的最长公共子串，每次只用判断一段区间内是否有某一子串的结尾位置。

线段树合并维护 \(S\) 的 \(\text{endpos}\) 即可。

配合 DSU on Tree/重链剖分

Luogu5576 [CmdOI2019] 口头禅

link

建立广义 SAM，每个字符串给对应的 SAM 点染对应颜色，我们要求的是同时包含 \([l,r]\) 所有颜色的子串长度最大值。

考虑倒序枚举每个子串，做 DSU on Tree，用 set 动态维护颜色连续段。

每合并出一个新段，我们拿这个段查一下，看看包含哪些询问区间，逐次更新即可。

Luogu4482 [BJWC2018] Border 的四种求法

link

要求的是 \(\max\limits_{i\in [l,r],\text{lcs}(i,r)\ge i-l+1}\{i\}\)。

建立前缀树，我们可以从 \(r\) 位置往上跳，然后查找子树内最大的合法的 \(i\)。

可惜会超时，还有另一种方法：询问离线，然后一遍 DFS，每次递归进入一个子树时，把其他子树的信息丢进一个线段树里。

用重链剖分平衡两种做法：

• 往上跳，跳轻边时，查询子树内最大的合法的 \(i\)，用线段树合并然后线段树二分即可。

• 对于重链，我们可以一遍 DFS，然后暴力把轻子树的点全部丢进线段树内。

时间复杂度 \(O(n\log n)\)。

CF1098F Ж-function

link

考虑我们要求的是 \(\sum_{i=l}^r \min(r-i+1,\text{lcp}(l,i))\)。

可以这样想：我们把 \([i,i+\text{lcp}(l,i)-1]\) 这一段 \(+1\)，然后查询 \([l,r]\) 的总和。

当然直接跳链也是可以的，用重链剖分平衡两种做法：

• 跳轻边时，查询子树，线段树合并。

• 对于重链，我们暴力加入轻子树的信息，然后对于询问，查询 \([l,r]\) 的总和。

注意查询时要剔除 \(i<l\) 的贡献，使用 CDQ 分治，时间复杂度 \(O(n\log ^3 n)\)。

CF 有 64bit 语言 可以过，但是 Luogu 不能过。