题目解析

问题理解

Bajtazar 想要用模板在墙上写出目标字符串 $s$。他有两个模板：

• 正模板：长度为 $m$ 的子串 $s[0:m-1]$
• 反模板：正模板的反转，即 $s[m-1:0:-1]$

他可以使用任意数量的这两个模板，可以重叠放置，但同一个位置的字母必须一致。目标是找到所有可能的模板长度 $m$，使得能够用这两个模板组合出整个目标字符串 $s$。

核心思路

1. 问题转化

对于每个可能的模板长度 $m$，我们需要检查：

• 能否用正模板（$s[0:m-1]$）和反模板（$s[m-1:0:-1]$）的多个实例覆盖整个字符串
• 覆盖时不能出现字母冲突

2. 关键观察

• 正模板只能放置在位置 $i$，如果 $s[i:i+m-1] = s[0:m-1]$
• 反模板只能放置在位置 $i$，如果 $s[i:i+m-1] = s[m-1:0:-1]$
• 我们需要检查这些位置的并集是否能覆盖整个字符串

3. 算法框架

步骤1：预处理字符串匹配信息

使用 Z算法 计算：

• z[i]：从位置 $i$ 开始的子串与整个字符串的最长公共前缀长度
• rz[i]：从位置 $i$ 开始的子串与反转字符串的最长公共前缀长度

步骤2：维护可用起始位置

使用 并查集数据结构 来高效维护：

• pos：可放置正模板的起始位置
• rpos：可放置反模板的起始位置

当 $m$ 增加时，某些起始位置变得不可用（因为匹配长度不够），需要从并查集中删除。

步骤3：贪心覆盖检查

对于每个 $m$，从左到右检查是否能覆盖整个字符串：

• 在当前覆盖位置 $x$，寻找不超过 $x+1$ 的可用起始位置
• 选择能覆盖到最右边的模板放置位置
• 如果无法继续覆盖，则 $m$ 不可行

算法复杂度分析

• Z算法预处理：$O(n)$
• 并查集操作：每个位置最多被删除一次，均摊 $O(\alpha(n))$ 每次操作
• 主循环：对每个 $m$ 进行贪心检查，总共 $O(n \log n)$ 或 $O(n \alpha(n))$

总复杂度：$O(n \log n)$ 或 $O(n \alpha(n))$，对于 $n \leq 10^6$ 是可接受的。

算法标签总结

1. 字符串匹配 - 使用 Z 算法预处理匹配信息
2. 并查集/Union-Find - 高效维护可用起始位置
3. 贪心算法 - 从左到右检查覆盖可能性
4. 扫描线思想 - 按模板长度从小到大处理
5. 动态维护 - 随着 $m$ 增大动态更新可用位置

代码实现亮点

1. 避免浮点数：全部使用整数运算
2. 高效数据结构：使用并查集快速查找可用位置
3. 事件驱动：按匹配长度组织删除事件
4. 贪心验证：线性时间检查每个 $m$ 的可行性

这个解法巧妙地结合了字符串算法和数据结构，通过预处理和动态维护，在合理时间内解决了大规模输入的问题。