题解：P12671 「TFXOI Round 2」String

· · 题解

本文给出在 询问非随机 情况下的做法。

本文的询问为“是否有长度为 l_1 的回文串，有长度为 l_2 的回文前缀”，与原题面有区别，请注意。

关于记号：子串 S[l,r]=S_lS_{l+1}\dots S_{r}

设 S[0,n] 为一长度为 n+1 的回文子串

设还有一个从 m 处开始、长度为 n+1 的、且与 S[0,n] 本质不同的回文子串为 S[m,m+n]

在后续，我们会证明，若 m\le\frac{n}{4}+C_1，则下一个与 S[0,n] 和 S[m,m+n] 本质不同的长度为 n+1 回文子串 S[o,o+n] 一定满足：o> \frac{n}{2}+C_2。C_1, C_2 为两个很小的常数（由于笔者懒得推）。

换而言之，长度为 n 的本质不同子串的平均分布密度最大为 \frac{4}{n}。对于一个长度为 N 的字符串，所有长度为 K 的本质不同字符串的个数最多为 O(\frac{N}{K})

对询问（是否有长度为 l_1 的回文串，有长度为 l_2 的回文前缀）去重后，考虑所有 l_1 相同的询问。对 PAM 上所有长度为 l_1 的本质不同回文子串，打上询问 tag l_2；在所有 l 打完 tag 后，在 PAM fail 树上 dfs，跑长度为 l_1 的回文子串结点是否有长度 l_2 的父亲。每一个询问最多贡献 O(\frac{N}{l_1}) 复杂度（由于只有 O(\frac{N}{l_1}) 个本质不同的回文子串）。

最大化时间复杂度，对 Q 个询问贪心的选 l_1 最小的。由于 l_1 最多只有 O(l_1) 个本质不同的询问，选择所有的长度为 l_1 的询问带来的贡献为 O(l_1)\times O(\frac{N}{l_1})=O(N)；你最多能完全选取 q=O(\sqrt{Q}) 个 l_1（1+2+\dots +q=Q, \frac{q(1+q)}{2}=Q），故总时间复杂度为 O(N\sqrt{Q})

设 S[0,n] 为一长度为 n+1 的回文子串

设还有一个从 m 处开始、长度为 n+1 的、且与 S[0,n] 本质不同的回文子串为 S[m,m+n]

若 m\le\frac{n}{4}+C_1，则下一个与 S[0,n] 和 S[m,m+n] 本质不同的长度为 n+1 回文子串 S[o,o+n] 一定满足：o> \frac{n}{2}+C_2

下面不加说明的，所有的 m 或 m' 均满足 m, m'\le\frac{n}{4}+C_1

由于 S[m,m+n] 是回文串，则 S[2m,n] 一定也是回文串。

这也说明，对于每一个回文串 $S[m',m'+n]$，对应到 $S[0,n]$ 中一定有周期 $S[0,2m'-1]$；若 $S[0,n]$ 有周期 $S[0,2m'-1]$，则 $S[m',m'+n]$ 才可能是回文串。 记 $S[0,n]$ 的最小周期为 $p$，最小偶数周期 $p'=p \text{ or } 2p$。$p'\le 2m\le \frac{n}{2}$。设 $p'=2P$，则 $P\le \frac{n}{4}

根据 border 和周期的那一套性质，我们只有 S[P,P+n], S[2P, 2P+n], \dots S[kP,kP+n] 才可能是回文串（对应有有周期 S[0,p'-1], S[0,2p'-1], \dots S[0, kp'-1]）。其中 k 为满足 kp'=2kP\le n 的最大正整数。kP 有 kP>\frac{n}{2}+C_2，否则 (k+1)p'\le n。

对于一个 S[k'P, k'P+n]，k'>0，在 S[k'P,n] 亦有周期 p'=2P。考虑回文中心 \frac{n}{2}+k'P\le n，这个周期 p' 成立的范围一定会经过回文中心。

在 S[0,n], S[P,P+n], S[2P, 2P+n], \dots S[kP,kP+n] 之中，最多重复出现 2 个本质不同的回文串。若有 3 个以及上的本质不同回文串，则一定有两个 k 的奇偶性相同，记为 k_1,k_2(k_1<k_2)，k_2=k_1+2\mu P。由于他们在回文中心之前周期均为 2P，起始周期 S[k_2P,k_2P+2P-1] 为 S[k_1P, k_1P+2P-1] 中的某一周期中的一段，故起始周期相同，回文中心之前相同，对称过去两串也相同。

下一个出现的本质不同回文串的位置 o 一定 o>KP>\frac{n}{2}+C_2

设 N,Q 同阶，我们可以构造出这个复杂度上界的字符串和询问。

我们用字符集大小 |\sum^*|=\infty 说明。考虑构造 \sqrt{N} 个长度为 \sqrt{N} 的回文字符串，使得所有回文串中中间的字符各不相同。询问 l_1=[2,\sqrt{N}], l_2=[1,l_1)，共 O(N)\sim O(Q) 个询问，每个询问对复杂度的贡献为 O(\sqrt{N})（\sqrt{N} 个长度为 l_1 的本质不同回文串），总复杂度为 O(Q\sqrt{N})\sim O(N\sqrt{Q})。

当 |\sum^*|=26 时，尽可能构造 \sqrt{N} 个离中间字符最近的字符各不相同的字符串。这样可以最大化长度较小时的本质不同回文串 。由于不同回文字符串的增速是指数的，复杂度相同。