上一次做 SA / SAM 相关的题还要数到某场毒瘤 NOIP 模拟赛……这么久没做了都快忘光了……写点东西记录一些最近做到的水好题。
LOJ2059 「TJOI / HEOI2016」字符串
题意
给定一个长度为 (n) 的字符串 (s) ，接下来有 (m) 次询问。每次询问给出四个参数 (a,b,c,d) 。求 (s[a,b]) 的所有子串和 (s[c,d]) 的 LCP 的最大值。
(n,m le 10^5) 。
题解
题目可以转化为，求一段连续的后缀与 (s[c,d]) 的 LCP 的最大值。由于这个最大值对位置还有一个限制，因此直接求不大好做，考虑二分答案转化为判定问题。
二分答案之后，就只需要查询，和 (s[c,d]) 的 LCP (ge k) 的后缀是否在一段区间内出现过。这样只要把 SA 建出来，就只需要查询一个区间内是否出现了某个区间内的数，直接按照 (rk) 建一棵主席树，就可以在 (O(n log^2 n)) 的时间内解决了。
SA + 主席树也是一个相当常见的套路，可以注意一下。另外 SAM 做这个题复杂度似乎没有优化？所以也没啥意义了。
UVA10829 L-Gap Substrings
题意
给定一个串 (S) 。求有多少 (S) 的子串是形如 (UVU) 的形式，且 (U) 不是空串，(V) 中恰好包含了 (g) 个字符。
数据组数 (T le 10,|S| le 5 imes 10^4,g le 10) 。
题解
考虑枚举 (U) 串的长度。这样我只要每隔 (|U|) 个放一个关键点。然后对于两两相邻的关键点，将后面的关键点强行往后移 (|V|) 的长度，检查以这两个关键点为结尾的串的 (mathrm{LCS}) 以及以这两个关键点开头的串的 (mathrm{LCP})，就可以快速统计对于某个串长的答案。这样利用 (mathrm{SA}) 就可以快速实现这个东西了，复杂度是 (O(n log n)) 的。
和刚刚那个题一样，先枚举产生贡献的串长，然后每隔固定长度放一个关键点。每次检查关键点的信息也是一个常见的套路。类似的题还有「NOI2016」优秀的拆分。
Codeforces 700E Cool Slogans
题意
给出一个长度为 (n) 的字符串 (s_1)。定义一个字符串序列 (s_{1 sim k}) ，满足性质：(s_i) 在 (s_{i - 1} (i ge 2)) 中出现至少两次，问最大的 (k) 是多少，使得从 (s_1) 开始到 (s_k) 都满足这样一个性质。
(n le 2 imes 10^5) 。
题解
首先建出 (mathrm{SAM})。于是我们只要从 (mathrm{SAM}) 的 (mathrm{fail}) 树上从根节点往下的一条路径中选出尽量多的节点，满足上一个点所代表的子串在这一个点至少出现了 (2) 次。由于一个点所代表的若干个集合的 (endpos) 集合是相同的，因此我们可以直接取这个点代表的所有子串中，长度最长的子串。
考虑从上往下不断贪心选点，那么这一个点能否被选择，只取决于这一个点代表的最长子串，是否包含了上一个被选择的点所代表的子串至少 (2) 次。这里可以考虑用线段树合并，来维护 (endpos) 集合。于是我需要对 (mathrm{SAM}) 上每个点多记录一个第一次扩展出当前节点的时间 (id_i)。这样就可以得到，这个节点所代表的字符串，对应原字符串的 ([id_i - len_i + 1,id_i]) 这样一个区间。假如我要查询节点 (u) 所代表的最长字符串在节点 (v) 代表的最长字符串出现了多少次，那么我只需要在 (u) 这个节点的线段树上查询 (endpos) 位于 ([id_v - len_v + len_u,id_i]) 这个区间内的和即可。
LOJ 2720 「NOI2018」你的名字
题意
给定一个模板串 (S) 。接下来会给出 (m) 个询问。每次询问给出询问串 (T) 和区间 ([l,r])。求 (T) 串有多少个本质不同的子串没有在 (S) 串的 ([l,r]) 中出现过。
(|S| le 5 imes 10^5,m le 10^5,sum|T| le 10^6) 。
题解
考虑枚举 (T) 串的每一个前缀 (T_{1,i})，求出这个前缀与 (S_{l,r}) 这个串的每个后缀的 ( ext{LCP}) 的 (max)，记为 (pre_i)。这样算答案的时候，我只需要枚举 (T) 串的 (mathrm{SAM}) 上每一个节点，这个节点对于答案的贡献即为 (len_i - max(len_{link_i},pre_{id_i}))。其中 (id_i) 同样表示 (i) 节点第一次扩展出来的时间。
如何求 (pre_i) 呢？这个同样可以通过建出 (S) 串的 (mathrm{SAM}) ，然后用线段树合并维护 (endpos) 集合。按照顺序枚举每个前缀，从 (pre_{i - 1} + 1) 开始尝试，记录包含当前这个长度的后缀在 (S) 串的 (mathrm{SAM}) 上深度最浅的点的位置 (u)，并且在线段树上查询以 (u) 为根的线段树上 (endpos) 位于 ([l + t,r]) 这个区间内的点是否存在，其中 (t) 为当前尝试的长度。如果匹配失败，就减少这个匹配的长度并再次尝试，直到匹配成功或者匹配长度减少为 (0) 则退出。时间复杂度是 (O((|S| + |T|) log n)) 的。
代码中最后统计贡献的时候对 (0) 取了 (max) ，而且这个 (max) 不取还会有问题，来解释一下原因。事实上克隆节点就相当于把某个节点的 ( ext{fail}) 拆出来了，这样克隆节点的 (len) 就会小于其扩展出来的时间，而 (pre_i) 上界是 (i) ，因此可能会被减到负数。
LOJ 6041 事情的相似度
题意
给定一个长度为 (n) 的 (01) 串，并定义第 (i) 个前缀，表示从第 (1) 个字符到第 (i) 个字符组成的字符串。接下来有 (m) 次询问。每次询问会给出一个区间 ([l,r]) ，查询第 (l) 个前缀到第 (r) 个前缀中，(mathrm{LCP}) 最大的一对前缀的 (mathrm{LCP})。
(n,m le 10^5) 。
题解
考虑建出这个串的 (mathrm{SAM})，这样问题转化为，每次询问一个区间内的点中，所有点对的 (mathrm{LCA}) 的 (len) 的最大值。注意到询问是可以离线的，因此考虑把询问按照右端点排序。
考虑如果我们维护出了每个节点的子树内出现时间最晚的点，姑且称作这个点的颜色，那么新加入一个点，从这个点到根节点的路径上，会经过若干段相同颜色的点，那么我只要在每一段深度最深的点处，在树状数组上修改一下。这个和 (mathrm{LCT}) 的 (access) 操作是一样的，可以方便地用 (mathrm{LCT}) 维护。查询的时候只需要在树状数组上查询即可。
当然直接在线也是有做法的。考虑用 ( exttt{std :: set}) 启发式合并维护 (endpos) 集合。每次新加一个数，产生贡献的肯定只会是这个数在 ( exttt{set}) 上的前驱后继。原因是，当前合并到这个区间，那么 (mathrm{LCA}) 的 (maxlen) 是固定的，这样产生贡献的点对编号差距尽可能小，才可能对更多的询问贡献。这样维护完之后，只需要再做一次二维数点，统计一个区域内的最小值即可。树状数组维护 (max) 的时候好像不太好删除，可以考虑把其中一维反过来，查询两维均小于等于某一个数的区域即可。
两种做法的复杂度都是 (O(n log^2 n)) 的。