CF1483F Exam

我永远喜欢数据结构

神仙 \(\color{maroon} *3400\) 字符串题。感觉现有的一篇 SA 题解讲的不太清楚，来一篇更加清楚、严谨的 SA 题解。

洛谷 CF

• 给出 \(n\) 个字符串 \(s_1\sim s_n\)，求有多少对 \((i,j)\)，满足：
  • \(1\le i,j\le n\)。
  • \(s_j\) 是 \(s_i\) 的真子串。
  • 不存在 \(k\)（\(i,j,k\) 两两不同）使得 \(s_j\) 是 \(s_k\) 的真子串，且 \(s_k\) 是 \(s_i\) 的真子串。
• \(n,\sum\limits_{i=1}^n|s_i|\le 10^6\)。若 \(i\ne j\)，则 \(s_i\ne s_j\)。
• \(\text{2 s / 512 MB}\)。

先将所有串拼成一个大串 \(S\) 进行后缀排序。考虑枚举 \(i\)，求出哪些 \(j\) 会产生贡献。

考虑对于 \(s_i\) 的每个后缀 \(s_i[x,|s_i|]\)，在 \(s_1\sim s_n\) 中，找到一个最长的字符串 \(s_y\)，满足它是 \(s_i[x,|s_i|]\) 的真前缀，记为 \(l_{i,x}=|s_y|\)。若找不到这样的 \(s_y\)，则称 \(l_{i,x}\) 无意义。若某个 \(l_{i,x}\) 能出现在等式或不等式中进行运算，当且仅当 \(l_{i,x}\) 有意义。

构造一个二元组不可重集合 \(T_i\)，一个二元组 \((u,v)\) 在 \(T_i\) 中出现，当且仅当满足以下四个条件：

• \(1\le u,v\le |s_i|\)。
• \(l_{i,u}\) 有意义。
• \(v=u+l_{i,u}-1\)。
• 不存在 \(w\in[1,u)\)，使得 \(u+l_{i,u}-1\le w+l_{i,w}-1\)。

称 \(s_j\) 在 \(T_i\) 中出现，当且仅当存在 \((u,v)\in T_i\) 使得 \(s_i[u,v]=s_j\)。

再构造一个二元组不可重集合 \(R_{i,j}\)，一个二元组 \((u,v)\) 在 \(R_{i,j}\) 中出现，当且仅当满足以下两个条件：

• \(1\le u\le v\le |s_i|\)。
• \(s_i[u,v]=s_j\)。

那么原题目中的二元组 \((i,j)\) 满足条件，当且仅当 \(\boldsymbol{R_{i,j}\ne \varnothing}\) 且 \(\boldsymbol{R_{i,j}\subseteq T_i}\)。

\(R_{i,j}\ne \varnothing\) 很显然，就不证了。

证明：

• 充分性：

  考虑反证，假设当 \(R_{i,j} \subseteq T_i\) 时存在 \(k\) 使得 \(s_j\) 是 \(s_k\) 的子串且 \(s_k\) 是 \(s_i\) 的真子串。

  设 \(s_i[a,b]=s_k\)，\(s_k[c,d]=s_j\)。那么 \(s_i[a+c-1,a+d-1]=s_j\)。根据已知条件可以得到 \((a+c-1,a+d-1)\in R_{i,j},T_i\)。

  若 \(l_{i,a+c-1}\ne d-c+1\)，则与 \((a+c-1,a+d-1)\in T_i\) 的第三个条件不符。

  否则，此时 \(c>1\)。根据 \(l_{i,a}\) 的定义可知 \(l_{i,a}\ge b-a+1\)，即 \(a+l_{i,a}-1\ge b\)。但是 \(a+c-1+l_{i,a+c-1}-1=a+c-1+d-c+1-1=a+d-1\)。根据 \(d\le b-a+1\) 可以得到 \(a+d-1\le b\)。与 \((a+c-1,a+d-1)\in T_i\) 的第四个条件不符。

  因此假设不成立。当 \(R_{i,j} \subseteq T_i\) 时一定不存在 \(k\) 使得 \(s_j\) 是 \(s_k\) 的子串且 \(s_k\) 是 \(s_i\) 的真子串。

• 必要性：

  考虑 \((u,v)\in R_{i,j}\) 但是 \((u,v)\notin T_i\)。此时 \((u,v)\) 一定满足某个二元组在 \(T_i\) 中的前两个条件。

  若 \(l_{i,u}\ne v-u+1\)，则有一个更长的字符串 \(s_y\) 为 \(s_i[u,|s_i|]\) 的前缀。此时 \(s_j\) 为 \(s_y\) 的真子串。

  否则，一定存在 \(w\in[1,u)\) 使得 \(u+l_{i,u}-1\le w+l_{i,w}-1\)。说明存在一个字符串 \(s_y=s_i[w,w+l_{i,w}-1]\)。此时 \(s_y\) 把 \(s_j\) 包含在中间，即 \(s_j\) 是 \(s_y\) 的真子串（能保证是真子串是因为 \(w\in[1,u)\)）。

  所以不满足 \(R_{i,j}\subseteq T_i\) 一定不会满足原来的条件，这是一个必要条件。

光有这个结论还不够，总不可能求出集合然后枚举判断。

进一步推理可以得到，它其实等价于 \(\boldsymbol{\sum\limits_{(u,v)\in T_i}P(s_i[u,v]=s_j)=|R_{i,j}|}\)。

为了区分中括号和艾弗森括号，使用 \(P(A)\) 表示 \(A\) 命题是否为真。当且仅当 \(A\) 为真命题时 \(P(A)=1\)；当且仅当 \(A\) 为假命题时 \(P(A)=0\)。

为什么呢？不难发现 \(\sum\limits_{(u,v)\in T_i}P(s_i[u,v]=s_j)=|T_i\bigcap R_{i,j}|\le |R_{i,j}|\)。而 \(|T_i\bigcap R_{i,j}|=|R_{i,j}|\) 等价于 \(R_{i,j}\subseteq T_i\)。

那么我们只需要对于一个 \(j\)，求出 \(\sum\limits_{(u,v)\in T_i}P(s_i[u,v]=s_j)\) 和 \(|R_{i,j}|\) 即可。

• 前者的求法：

  首先要得到 \(T_i\)。可以考虑对于每个字符串 \(s_a\)，它会对哪些排名的后缀的产生贡献。这个后缀要包含 \(s_a\)，等价于两者 \(|\text{LCP}|\ge |s_a|\)。可以维护 \(\text{height}\) 数组的 ST 表然后二分得到排名区间，让这个区间内的 \(l\) 值对 \(|s_a|\) 取 \(\max\)。线段树维护即可。

  然后就可以从左往右扫，维护前缀的 \(u+l_{i,u}-1\le w+l_{i,w}-1\) 最大值 \(pre\)。在线段树上单点查询当前后缀排名那个位置的值得到 \(l_{i,x}\)。若 \(x+l_{i,x}-1>pre\)，则将 \((x,x+l_{i,x}-1)\) 加入 \(T_i\)。

  然后使用桶维护 \(T_i\) 中 \(s_1\sim s_n\) 中每种字符串各作为多少个后缀的最长前缀。

• 后者的求法：

  考虑 \(s_j\) 作为某个后缀的前缀出现，同样可以求出包含它的后缀排名区间。然后变成求区间内有多少个排名使得这个排名的后缀来自于编号为 \(i\) 的字符串。

  对于每个 \(i\) 用一个 vector 从小到大存放其后缀出现的位置，二分得到左右端点 \(l,r\)，答案即为 \(r-l+1\)。

这样仍需要枚举 \(j\)。但你注意到：

由于 \(R_{i,j}\ne \varnothing\)，那些没在 \(T_i\) 中出现的 \(s_j\) 一定没有贡献。因为此时 \(|T_i\bigcap R_{i,j}|=0< |R_{i,j}|\)。只需要考虑那些在 \(T_i\) 中出现的 \(s_j\)。而对于每个 \(u\)，只会有一个 \(v\) 使得 \((u,v)\in T_i\)，因此 \(|T_i|=\mathcal{O}(|s_i|)\)。这样一来总共只需要处理 \(\mathcal{O}(|S|)\) 次。

为了不算重算漏，考虑对于每个在 \(T_i\) 中出现的字符串，在其第一次出现的位置统计。

最后对 \(s_1\sim s_n\) 的每个字符串都这样做一遍，就能得到正确答案了。

时空复杂度均为 \(\mathcal{O}(|S|\log |S|)\)。常数巨大，喜提最劣解，空间还是压线过的。时间估计是拼接字符串自带 \(2\) 倍以及线段树的 \(4\) 倍导致的。空间的话估计是我线段树合并信息写法的问题，应该可以再省个十几 \(\text{MB}\)。被 ACAM 打爆了 /ll。

AC code

接下来是一点闲话：

这题原来叫 Exam 啊，我想起了我刚考完的期末考试。哎，输得一塌糊涂，就像 OI 一样失败。我这辈子赢不了，只能度过一个不玩原神的失败人生了呜呜 /ll。