P10272 在四方城外 题解

· · 题解

String Round Rank 6 纪念，场切了此题，写篇题解。

题目涉及了 Border，显然可以跟 KMP 结合，此外就是一些分类讨论了。

 

性质

  1. 长为 n 的字符串 S 为周期字符串等价于：存在长为 k 的字符串 T，满足：k|n，S 与 \frac nk 个 T 拼接而成的字符串等价。k 被称为 S 的一个周期。
  2. 满足条件一的最小的 k 被称为字符串 S 的最小周期。
  3. 若长为 n 的字符串 S 为周期字符串，记其最长真 border 的长为 m，若 S 存在周期 n-m，则 n-m 为 S 的最小周期。

这些性质的证明可以见有关 KMP 的文章。

 

分类讨论

我们使用 KMP 求出 S 的最长真 border T，令 n=|S|,k=|T|，下面对 T 进行分类讨论。

1：T 为空

显然每次根本无法拓展，答案即为 (R-L+1)n。

2：|T| 为 S 的一个周期

假设已用 KMP 求出最长真 border T，判断 k 是否为 S 的周期是简单的。

由于拓展的字符串需要是真 border，每次拓展的长度即为 |S'|-k，拓展 i 次后的 |S'| 即为 2^in-(2^i-1)k，求和得 (2^{R+1}-2^L)(n-k)+(r-l+1)k，快速幂计算即可。

3：T 不是周期字符串

注意：此情况的前提是不满足前两个情况。

显然每次拓展的长度均为 k，拓展 L 次后长度为 n+Lk，R 次后长度为 n+Rk，求和得 (R-L+1)n+\frac{(L+R)(R-L+1)}2k。

4：T 是周期字符串

注意：此情况的前提是不满足前两个情况。

此情况的讨论应该是最容易漏掉的一种，T 是否是周期字符串跟 S 是否是周期字符串同理，容易判断。

设 T 的最小周期为 p，且 S[1:p] 在 S 的前缀中重复了 a 次，S[1:p] 在 S 的后缀中重复了 b 次。

例如：S=abababcabab，则 T=abab，p=2，S[1:p]=ab 在 S 的前缀中重复了 a=3 次，在 S 的后缀中重复了 b=2 次。

这时的拓展情况应该是怎样的呢？不难发现每次向后拓展 \min(a,b) 个 S[1:p]。

将 \min 拆开助于思考：

  1. 在 a\geqslant b 时，每次拓展 b 个 S[1:p]，同时 b\leftarrow 2b，这样的拓展不超过 \log_2n 次，可以暴力枚举。
  2. 在 a<b 时，每次拓展 a 个 S[1:p]，由于 a 这个数值不会变，所以容易计算出。

具体地，计算第一部分暴力维护长度 S' 和拓展次数 i，若 i\in[L,R]，将答案加上 S'。第二部分仅在 R>i 时有贡献（i 是完成第一部分的拓展次数），由于每次拓展长度固定，可以用情况三的式子计算。

容易发现第三种情况和这种情况类似，可以令 a=b=1,p=k，合并到一起计算。