Contest Info

practice link

Solutions

A. Password Suspects

题目大意：给定 \(n,m\)，以及 \(m\) 个长度在 \(10\) 以内的字符串（仅由小写字母组成）。问有多少个长度为 \(n\) 的字符串，同时以这 \(m\) 个字符串为子串。如果不超过 \(42\) 个，那么输出方案。\(1\leq n\leq 25,0\leq m\leq 10\)。

题解：将所有的给定串插入 ac 自动机，构建一个 trie 图，在 trie 图上进行 dp。trie 图的每个节点记录一个集合 \(f[p]\)，表示哪些给定串是节点 \(p\) 的后缀。因为给定串一定是 trie 图的前缀，所以我们插入的时候在终止节点插入元素，然后沿着 fail 链向下合并。也即 \(f[p] = f[p] \cup f[fail[p]]\)。 \(dp[p][len][s]\) 表示从节点 \(p\) 开始，当前长度为 \(len\)，当前包含给定串集合为 \(s\) 的方案数量。从 \(dp[\text{root}][0][\emptyset]\) 开始自顶向下 dp。

C. Regular Number

题目大意：给定一个形如 (0|9|7) (5|6) (2) (4|5) 的正则表达式。输入一个 \(n(\leq 1000)\)，接下来 \(n\) 个 \(a_i(1\leq a_i\leq 10)\) 表示每个位置的候选字符个数，以及 \(a_i\) 个候选字符。输入一个长度不超过 \(5\times 10^6\) 的字符串，输出所有匹配的子串。

题解：Shift-And 算法。

Algorithm Detail

算法的目的是保持一个集合 \(D=\overline{d_{m-1}\dots d_0}\)，表示模式串 \(p\) 的哪些前缀被到目前为止的文本串后缀匹配，当 \(d_{m-1}\) 有效的时候，我们得到一个匹配。

首先预处理表 \(B\)，对于 \(p\) 的每种字符处理一个 \(\overline{b_{m-1}\dots b_0}\)，表示其在模式串中的出现位置。例如 announce 中，字符 n 的表 00100110。表示位置 \(1,2,5\) 有字符 n。表中还需要添加一个空集 \(\emptyset\) ，表示匹配失败。

初始化 \(D=0\) ，依次扫描文本串，更新状态为 D <- ((D << 1) | 1) & B[current-char]。先左 shift 一位，表示不考虑当前字符匹配的集合 \(D\)，因为空集 \(\emptyset\) 一定匹配成功，所以我们还要或上一个 \(1\)，接着 and 上当前字符的出现位置。

E. Circular Palindromes

题目大意： 给出长度为 \(n(n\leq 5\cdot 10^5)\) 的字符串 \(S\)（只由小写字母组成），\(S_k\) 表示 \(S\) 循环左移 \(k\) 位后的字符串。要求输出 \(S_0,\cdots,S_{n-1}\) 的最长回文子串长度。

题解： 令 \(T=S+S\) ，问题转化为 \(n\) 次询问区间最长回文串长度。二分答案，如果区间 \([L+m-1,R-m+1]\) 中存在奇回文半径大于等于 \(m\) 的位置，那么就存在长度为 \(2m-1\) 的奇回文串，同理可以处理偶回文串。通过 Sparse-Table 预处理，可以使整个问题的时空复杂度均变为\(\mathcal{O}(n\log n)\)。

F. Forensic Examination

题目大意：给定一个串 \(s(|s|\leq 5\cdot 10^5)\)，以及 \(m(m\leq 5\cdot 10^4)\) 个串 \(t_i(\sum|t_i|\leq 5\cdot 10^4)\)，都仅由小写字母组成。接下来 \(q(q\leq 5\cdot 10^5)\) 个询问 \(l,r,p_l,p_r\) ，询问在串 \(t_l,\dots,t_r\) 中，哪个串中 \(s[p_l\dots p_r]\) 出现次数最多，输出串编号和出现次数。如果有次数相同的，输出编号最小的。

题解：令 \(T=s+\text{@}+t_1+\text{@}+t_2+\text{@}+\cdots +\text{@}+t_m\)，构建后缀自动机。把后缀自动机的 parent 树抽出来，每个节点用一个动态加点的线段树，维护区间 \([1,m]\) 的最大值，记录当前节点表示的字符串被串 \(t_i(1\leq i\leq m)\) 包含的最大次数。

动态构建 SAM 的时候，在每个真节点上记录当前位置在 \(\{t_i\}\) 的哪个串中。然后从根开始 dfs 这棵 parent 树，对于每个真节点，在它的线段树对应位置（所属的串编号）加一，回溯的时候合并子树。

还要记录串 \(s\) 的每个前缀 \(s_i\) 对应的节点 \(\text{pos[i]}\)，对于每个询问 \(l,r,p_l,p_r\)，我们从 \(\text{pos[}p_r\text{]}\) 向上倍增查找到 \(s[p_l\dots p_r]\) 所属节点，在它对应的线段树中询问 \(l,r\)。

G. Palindromic Border

题目大意：定义一个串的 Palindromic Border 如下：

• 它是回文的
• 它既是原串的前缀，也是原串的后缀

求给定串的所有子串（只要起始的位置不同就认为是不同的子串）的 Palindromic Border 的个数之和。

题解：建出原串的回文树，搞出所有本质不同的回文子串和其出现次数，则每种回文子串的贡献就是\(\displaystyle \binom{k}{2}\)，\(k\) 是该子串在原串中出现的次数。

H. Yong Zheng’s Death

题目大意：给出一个字符串集合 \(S = \{ s_1, s_2, \dots, s_n \}\)，\(|s_i| \leq 30,n\leq 10^4\) 。从 \(S\) 中任取两个串的前缀拼成一个字符串，问共有多少个本质不同的串。

题解：对 \(S\) 建一个 ac 自动机，得到 \(S\) 中本质不同的前缀共有 \(\text{cnt}\) 个，则答案为 \(\text{cnt}^2\) 减去重复的情况。

考虑计算重复的情况。对于最终得到的一个串 \(C = A_1 + B_1 = A_2 + B_2 = \cdots = A_k +B_k\) ，\(A_i\) 和 \(B_i\) 的拼接线为 \(l_i=|A_i|\)，我们规定 \(l_i\) 最小的方案是合法的，其它的视为重复方案。

我们枚举合法方案对应的 \(B\) ，显然所有不合法方案的 \(B'\) 都是它的一个后缀。而 \(B'\) 是 \(S\) 中的一个前缀，所以我们可以通过自底向上遍历 \(B\) 的 fail 链，找到所有的 \(B'\)。但并不是所有的 \(B'\) 都有对应的 \(A'\)，满足 \(A'+B'=A+B\)。

对于合法的 \(B'\)，我们设 \(X\) 满足 \(B=X+B'\)，那么有 \(A'=A+X\)。我们只需要知道满足条件的 \(A'\) 的数量，也即 \(S\) 中以 \(X\) 为后缀的前缀数量，这就是 \(X\) 所在 fail 树的子树大小（注意减掉 \(X\) 自身的情况，\(A\neq \emptyset\)）。因为串的长度不超过 \(30\)，我们只需要遍历 \(B'\)，然后从 \(B\) 暴力往上爬找到 \(X\) 即可。

L. The Problem to Slow Down You

题目大意：给出两个只有小写字母的字符串，求这两个串有多少对公共子串是回文的。

题解：对两个串分别建回文树，然后在两棵树上从根 0 和根 1 各进行一次 dfs。每个位置的贡献就是 A.cnt[x] * B.cnt[y]。