题解：P3526 [POI 2011] OKR-Periodicity
im_gay
·
·
题解
可能是题解区最易懂的 严谨 题解？
题意：给定字符串 s，构造一个 \texttt{01} 字符串 t，使得 |s|=|t| 且 s,t 的周期集合完全相同。同时，t 的字典序尽可能小。
引理 1. 一个长度为 n 的字符串存在周期 t，当且仅当其存在长为 n-t 的 border。
引理 2.（弱周期引理） 一个长度为 n 的字符串同时存在周期 p,q 且 n \ge p+q，则其也存在周期 \gcd(p,q)。
一个字符串的周期集合和其 border 集合构成双射（由 引理 1），而 border 集合可以用 KMP 算法求出。考虑最长的 border B。
由于 B 是一段前缀，且我们希望字典序最小，容易想到先递归处理长度为 B 的子问题，再考虑拼出原串。
设 |s|=n，当 2B \ge n 时，无需构造，下仅考虑 2B < n 的情况。
由于 B 是最长的 border，我们的方案只需要满足 不会出现比 B 更长的 border C 即可。
我们假设存在这样的 C。按 C 长度分类讨论：
其中 $D$ 表示 $s$ 去掉两个最长 border $B$ 后的串，满足 $s=BDB$。
此时我们希望 $D$ 的字典序尽可能小，先令 $D$ 全 $\texttt 0$。我们通过简单推导，不难发现整个串全 $\texttt 0$。
所以当 $B$ 不全 $\texttt 0$ 时，我们可以令 $D$ 全 $\texttt0$；否则，可以令 $D$ 的最后一位为 $\texttt 1$，这样就不存在如图的 $C$ 了。
$2|C|>n$ 的情况同理，不再展开。
+ $|B| + |C| > n
其中 C 实际是绿色、蓝色的拼接串。同理，先令 D 全 \texttt 0。
由于 B,C 均为 border，则 n-|B|, n-|C| 均为 s 的周期；由 引理 2，从 n-|B|+n-|C| \le n 可得 T=\gcd(n-|B|,n-|C|) 为原串周期。不难发现 T \le n-|C| < |B|。
图示的是 T>|D| 的情况，不妨令 T=|D|+|P|。这种情况下，我们发现
B=PDPD\dots PDP
如果 B 满足这种模式，我们不得不令 D 最后一位为 \texttt 1；否则可以让 D 全 \texttt 0。
剩余的一种情况是 T \le |D|，这种情况说明原串全 \texttt 0。如果 B 不全 \texttt 0 是不会发生的，否则（如果 B 全 \texttt 0）我们令 D 最后一位为 \texttt 1。这样，如果 C 仍存在就说明全局至少有两个 \texttt 1，——这显然是不可能的。
综上，做法就是（只考虑 2|B|<n）：
- 当 B 全 \texttt 0 时，令 D 最后一位为 \texttt 1，其他全 \texttt 0；
- 当 B 不全 \texttt 0 时，检查 B=PMPM\dots PMP 是否满足，其中 M 为长度为 n-2|B| 的全 \texttt 0 串：
- 若不满足，令 D=M；
- 若满足令 D 最后一位为 \texttt 1，其他全 \texttt 0。
实现上，我们可以先令 D=M 并跑一遍 KMP 求是否存在 border 的长度 >|B|，如果存在则不合法，令 D 最后一位变为 \texttt 1。上述“做法”仅是证明此方法的严格正确性。
当然，若原串没有 border，直接令原串最后一位为 \texttt 1 其余为 \texttt 0 即可。
这样 T(n) = T(\frac{n}{2}) + \mathcal O(n) 得到总复杂度 \mathcal O(n)。