CF319D 题解

题意

给你一个字符串 \(S\)，要求你每次找到一个最短的并且最左边的形如 \(XX\)（即由两个相同的字符串拼接而成）的子串，然后把这个字符串从 \(XX\) 变成 \(X\)。问无法操作后的字符串是什么？

\(|S|\le5\times 10^4\)。

首先有一个重要的结论是：设每次删去的串 \(XX\) 长为 \(2\times len\)，则 \(len\) 是递增的。

因为如果将 \(XX\) 替换成 \(X\) 后出现更小的 \(len\)，则其必包含 \(X\) 的前缀或后缀。而实际上这部分也被包含于 \(XX\)。故矛盾。

于是我们可以从小到大枚举 \(len\)，每次删去长度为 \(2 \times len\) 的。复杂度为 \(O(n^2)\)。

但这还不够。有什么方法更优呢？

注意到如果每次能够 \(O(1)\) 判断当前 \(len\) 能否删，复杂度是 \(O(n \sqrt n)\) 的。因为 \(len\) 递增，所以能删的 \(len\) 不超过 \(\sqrt n\) 个。

如何快速判断是否有长度为 \(2 \times len\) 的 \(XX\)？这里需要用到一个强大的 trick。

每 \(len\) 个单位设置一个观察点，对每相邻两个观察点求 \(lcp\) 与 \(lcs\)。如果存在两个相邻的观察点的 \(lsp+lcs>len\)，那么就存在。

证明不难。实际上这个方式判断的是长度 \(\ge 2 \times len\) 的 \(XX\)，但因为我们从小到大枚举，故等价。

这样判断的复杂度是 \(O(n\log^2n)\) 的。足以通过此题。