CF526D Om Nom and Necklace

Description

给定长度为 n 的字符串 s ，对于 s 的每个前缀，求该前缀是否能满足 AB...ABA 的形式，其中 A 恰好有 k+1 个，B 恰好有 k 个 。A B 可以是任意字符串，或者为空串；k 是给定的。
$1\leq n,k\leq 10^6$

Solution

非常直观的想法就是将 AB 视作一个整体，再在最后加个 A 。
由于 k 是给定的，当循环节长度也给定时，前缀是确定的。故我们可以枚举循环节长度 c ，然后判定 s[1:ck] 是否为循环节次数为 k 的严格循环子串。如何快速判定呢？考虑当 s[1:ck] 符合要求时， s[1:c(k-1)]=s[k+1:ck] ，并且互为充分必要条件。正着非常直观，反过来证明可以这样考虑：s[1:k]=s[k+1:2k]=s[2k+1:3k]=... 。类似于错位相消？ 🤔

由上可知一个重要的 trick ：

$\text{Z}_{k}\ge$ c(k-1) 与 s[1:ck] 为循环节次数为 k 的严格循环子串互为充要条件。

插句闲话，如果要判断 s[l,r] 是否为循环节长度为 k 的严格循环子串时可以哈希判断 s[l:r-k] 和 s[l+k:r] 是否相等。证明方法与上述错位相消类似。

回到这个题，我们已经求出来了所有循环节长度恰好为 c 的位置，现在再考虑如何在 s[ck] 后插入 A 。显然， A 的长度小于等于 c ，并且在 c 中出现过。这不恰好就是 $\text{min}(\text{Z}_{ck+1},c)$ 嘛。并且可以发现是一整段一整段的符合条件，所以直接差分维护就行了。
算法复杂度 $\mathcal{O}(n)$ 。

事实上，对于 ABA...A 的串，一种更加直观的想法是直接 kmp 求 border 。kmp 求出来的非严格循环节形式上也更像。但是由于此题限制了循环次数为 k ，似乎除了暴力跳 fail 也没有什么好的枚举办法。
其实不然。我们设当前枚举到第 i 位。当前的最长 border 为 fail[i] ，周期为 T=i-fail[i] ，循环次数为 d=i/(i-fail[i]) 下取整。鉴于我们需要的循环次数为 k ，我们直接钦定每 d/k （下取整） 个小循环为一个大循环， 剩下的 d mod k 个小循环为 A 。
当 i 恰好为若干次小循环时，B 可以为空串；否则的话，B 不能为空串。
算法复杂度也是 $\mathcal{O}(n)$ 。

代码采用的是第二种方法。

Code

for(int i=1;i<=len;++i){
        int d=i/(i-fail[i]);
        if(i%(i-fail[i])) putchar((d/k-d%k>0)+'0');
        else putchar((d/k-d%k>=0)+'0');
    }