自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:30:42，当前版本为作者最后更新于2021-04-15 23:52:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果没有 border，答案是 $n$。

如果有整周期，则答案是 $|p|+2^K(n-|p|)$，其中 $p$ 是最小整周期。

如果 border 大于 $\dfrac n2$，即周期小于 $\dfrac n2$。令 $s=p^k\cdot pre_t(p)$，其中 $p$ 是最小周期，$pre_t(p)$ 是 $p$ 的长为 $t$ 的前缀（$0<t<|p|$）。实际上这样的字符串进行一次操作之后的最长 border 仍为 $n-p$，证明如下：

假设进行一次操作后的字符串有一个长度小于 $n$ 的周期 $q$，首先我们知道 $p\nmid q$，因为如果 $q$ 是 $p$ 的倍数的话就间接指出 $p^\infty=pre_t(p)\cdot p^\infty$，则 $t$ 是 $p$ 的整周期，$p$ 就不是原串的最小周期了。于是我们知道 $q>\dfrac n2$，因为 $p\nmid q$，如果 $q\le \dfrac n2$，则会必然会有一个小于 $p$ 的周期（弱周期引理）。不难发现由于 $|p|\le\dfrac n2$，于是 $k>1$，那么根据周期的定义，我们知道 $q=suf_{n-|q|}(s)\cdot pre_{2|q|-n}(p^\infty)$（把 $q$ 重复两次和串匹配），于是我们得知 $(|q|\bmod|p|)$ 和 $(|p|-(|q|\bmod|p|))$ 同为 $p$ 的周期，进而通过周期引理我们知道 $p$ 必然有一个长为 $g=(|q|\bmod|p|,|p|)$ 的周期，而由于 $g<|p|$ 且 $g\mid(|p|)$，我们知道 $g$ 是 $p$ 的一个整周期，则 $g$ 也是原串的一个周期且长度小于 $p$，形成矛盾。于是我们得证。

这样的话，一个周期小于 $\dfrac n2$ 的字符串经过一次操作之后 border 仍为 $n-p$，那么此时的最短周期就为 $n+(n-p)-(n-p)=n>\dfrac{n+(n-p)}2$。于是我们现在只需要讨论周期大于 $\dfrac n2$ 的情况。

对于这种情况，即 $k=1$，我们有一个结论。令 $B$ 为 $s$ 的最长 border，$l$ 为 $B$ 的最小整周期，令 $B=l^j$，然后找到最大的 $i$ 使得 $pre_{i|l|}(s)=l^i$。首先 $i|l|<n+|l|$，因为反之的话，首先我们知道 $|l|\nmid n$（$s$ 有一个整周期的情况我们已经在题解最开始讨论过了），于是我们知道 $i|l|-n\ge |l|$，不妨令 $n\equiv q\pmod{|l|}$，则 $suf_{|l|-q}(l)$ 既是 $l$ 的周期也是 $l$ 的 border，于是 $l$ 会有一个更小的整周期，形成矛盾。

有个结论：我们进行第 $b$ 次操作后的最长 border 长度为 $\min\{2^bj,i\}|l|$。考虑归纳证明。$b=0$ 时显然，我们考虑 $b>0$。在进行这一操作前的字符串，假令其长度为 $n$，我们知道最长 border 长度是 $\min\{2^{b-1}j,i\}|l|$ 的，那么显然进行这一操作后的字符串会有一个长为 $\min\{2^bj,i\}|l|$ 的 border，我们只需要证明不存在一个比其更长的 border。

• $i\ge2^bj$：则如果存在 $|\text{border}|>2^bj|l|$，则存在 $|\text{周期}|<n+2^{b-1}j|l|-2^bj|l|=n-2^{b-1}j|l|$，而我们知道进行操作前的字符串 $\text{周期}=n-2^{b-1}j|l|$，形成矛盾。
• $i<2^bj$：我们考虑把这个 border 和 $s$ 的前缀进行匹配。
  • $|\text{border}|=l^k$：这意味着 $l^k=l^i\cdot s_{[i|l|,k|l|]}$。由于 $k>i$，这显然不可能，因为这意味着 $pre_{(i+1)|l|}(s)=l^i$，则我们的 $i$ 是应该更大的，产生矛盾。
  • $|\text{border}|\ne l^k$：假令 $|\text{border}|\equiv q\pmod l$，$|\text{border}|=d$，则我们得到 $l^i\cdot s_{[i|l|,d]}=suf_q(l)\cdot l^{\left\lfloor\dfrac d{|l|}\right\rfloor}$。由于 $\dfrac{d}{|l|}\ge i$，我们知道 $l=suf_q(l)\cdot pre_{|l|-q}(l)$，即 $q$ 既是 $l$ 的周期也是 $l$ 的 border，则 $l$ 有一个更小的整周期，产生矛盾。

于是我们只需要找到 $i,j$ 后直接模拟即可，时间复杂度 $O(n+\log K)$（$s$ 有整周期时的快速幂）。

mivik.h / 代码