「POI2011 R3」周期性 Periodicity 题解

题目简述

给定一个大写字母串（人名），要求把它转换为同样长度的 $01$ 串，且满足：

长度相同

与原串有相同的周期集合

字典序最小

如果无解则输出 XXX。

什么是周期？ 对于长度为 $n$ 的字符串 $s$，一个整数 $p\ (1 \le p < n)$ 是周期，当且仅当对于所有 $i = 1 \dots n-p$，都有 $s[i] = s[i+p]$。

即前 $n-p$ 个字符和后 $n-p$ 个字符完全匹配。

核心思想

关键性质

字符串的周期集合完全由其前缀函数或 KMP 的 fail 数组决定。

具体来说，字符串 $s$ 的长度为 $n$，$fail[i]$ 表示 $s[1..i]$ 的最长相同真前缀后缀长度。则 $p$ 是 $s$ 的周期 ⇔ $n-p$ 在 $fail$ 数组的值中（或者说 $p = n - fail[n], n - fail[fail[n]], \dots$）。

所以问题转化为 给定 $fail$ 数组，构造字典序最小的 $01$ 串，使其 $fail$ 数组与给定相同。

算法步骤

1. 先判断可行性 并不是所有 $fail$ 数组都能对应一个合法字符串。需要检查：

$fail[1] = 0$

对于 $i \ge 2$，要么 $fail[i] = 0$，要么 $fail[i] = fail[i-1] + 1$，要么 $fail[i] \le fail[i-1]$ 且有对应的字符匹配关系。

实际上更简单的方法：如果 $fail[i] \neq 0$，则 $s[i] = s[fail[i]]$。

所以我们可以推导出原字母串中哪些位置的字符必须相同，把它们分组。

2. 构造最小字典序 $01$ 串 我们从左到右构造：

设现在处理到第 $i$ 位

如果 $fail[i] \neq 0$，则 $s[i]$ 必须等于 $s[fail[i]]$，直接复制过来

如果 $fail[i] = 0$，我们可以自由选择 $s[i]$。为了字典序最小，我们总是先尝试填 0，如果填 0 会导致后面某个位置矛盾（即导致 $fail$ 数组不对），才填 1

3. 判断矛盾 填完 $s[i]$ 后，要更新它对后续位置 $fail$ 值的影响。 更具体地说，当我们确定了 $s[i]$，要检查所有 $fail[j] = i$ 的 $j$ 是否满足 $s[j] = s[i]$（如果 $fail[j] \neq 0$ 时）。若不满足且 $fail[j]$ 已经确定，则无解。

4. 用并查集维护相同关系 把必须相同的字符位置用并查集合并。在尝试填 0 时，如果该位置的集合已经固定为 1，则不能填 0。

具体算法

读取原字母串，忽略具体字母，只根据相同字母出现模式得到哪些位置必须相同

即如果原串中 $s[a] = s[b]$，则在新 $01$ 串中位置 $a$ 和 $b$ 必须同字符（0 或 1 相同）

如果 $s[a] \neq s[b]$，则位置 $a$ 和 $b$ 必须不同

实际上我们不必依赖原字母，而是根据 fail 数组推导等价关系。

通过 KMP 算法得到原串的 fail 数组 $f$。

从 $i=1$ 到 $n$ 构造：

如果 $f[i] \neq 0$，则 $ans[i] = ans[f[i]]$

如果 $f[i] = 0$，则尝试填 0，判断是否矛盾；矛盾则填 1，再判断是否矛盾；都矛盾则无解（输出 XXX）

输出构造的 $01$ 串。

复杂度分析

计算 fail 数组：$O(n)$

构造答案并查集维护：$O(n \alpha(n))$

总复杂度：$O(n)$