字符串合集

Problem A. P7409 SvT

题意：

给定一个长度为 \(n\) 的小写英文字符串 \(s\) 和 \(q\) 次询问。每次给一个大小为 \(k_i\) 的整数集合，询问集合内两两不同数代表的后缀的 LCP 的长度和，对大质数取模。

\(1 \leq n \leq 5 \times 10^5\)，\(1 \leq \sum k_i \leq 3 \times 10^6\)，时限 \(3\) 秒，空间限制 \(512\) MB。

解法：

刻画后缀 LCP 的常见做法有很多。

一个做法是，考虑后缀排序，根据 SA 相关结论，两个后缀的 LCP 等价于区间 \(\min\)。询问时先进行相邻的 RMQ，然后单调栈求值即可。

另一方面，仍然考虑 SA，但是将区间 \(\min\) 刻画为笛卡尔树上 LCA 点权，显然对询问点建虚树即可。

不用 SA，直接考虑后缀树。容易发现后缀 LCP 等于后缀树上 LCA 到根路径长，进一步等于反串 SAM 的 Link 树上 LCA 的等价类最大长度。所以同样对询问点建虚树即可。

Submission Link.

Problem B. CF1090J Two Prefixes

题意：

给定字符串 \(s,t\)，求 \(s\) 非空前缀与 \(t\) 非空前缀拼接后得到的本质不同字符串个数。

\(1 \leq |s|,|t| \leq 10^5\)，字符集为小写英文字母。

解法：

假设 \(n = |s|\)，\(m = |t|\)。

考虑对于每个本质不同字符串，在最小的 \(s\) 的前缀位置统计答案。

不难发现对于每个 \(i\)，有且仅有一段后缀 \([j,m]\) 符合 \(s[1 \cdots i]+t[1 \cdots j]\) 是之前没有出现过的。我们考虑二分这个 \(j\)，问题变为给定 \(i,j\)，判断是否存在 \(x < i\) 使得 \(s[1 \cdots x]+t[1\cdots i+j-x]=s[1 \cdots i]+t[1 \cdots j]\)。容易发现本质相当于我们找到 \(s[1 \cdots i]\) 的某个后缀，其与 \(t\) 的某个前缀相等，然后把 \(t[1 \cdots j]\) 往后平移相同。

将 \(t\) 与 \(s\) 拼在一起，中间加个特殊符号。那么我们要找的后缀其实就是 Fail 树上的祖先。但是如果我们选了 \(s[1 \cdots i]\) 的一段长度为 \(k\) 的后缀，还需要判断 \(t[1 \cdots j]=t[k+1\cdots k+j]\) 是否成立。注意到这等价于 \(\operatorname{LCP}(t,t[k+1\cdots m]) \geq j\) 是否成立。于是先对 \(t\) 做一下 exKMP，然后在树上预处理每个点到根的点权最大值即可做到 \(O(1)\) 判定。

实际实现中不需要显式建树。

Submission Link.