SA / SAM 题目集

2019/01/09 16:45
阅读数 47

上一次做 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 \times 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 \times 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 \times 10^5,m \le 10^5,\sum|T| \le 10^6$ 。

题解

考虑枚举 $T$ 串的每一个前缀 $T_{1,i}$,求出这个前缀与 $S_{l,r}$ 这个串的每个后缀的 $\text{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$ 不取还会有问题,来解释一下原因。事实上克隆节点就相当于把某个节点的 $\text{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}$ 维护。查询的时候只需要在树状数组上查询即可。

当然直接在线也是有做法的。考虑用 $\texttt{std :: set}$ 启发式合并维护 $endpos$ 集合。每次新加一个数,产生贡献的肯定只会是这个数在 $\texttt{set}$ 上的前驱后继。原因是,当前合并到这个区间,那么 $\mathrm{LCA}$ 的 $maxlen$ 是固定的,这样产生贡献的点对编号差距尽可能小,才可能对更多的询问贡献。这样维护完之后,只需要再做一次二维数点,统计一个区域内的最小值即可。树状数组维护 $\max$ 的时候好像不太好删除,可以考虑把其中一维反过来,查询两维均小于等于某一个数的区域即可。

两种做法的复杂度都是 $O(n \log^2 n)$ 的。

展开阅读全文
lcp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部