D. 串联重复串? 详细题解

题目核心理解

给定一个由小写字母和问号 ? 组成的字符串 $s$。 你可以把每个问号替换成任意小写字母。

串联重复串定义为：长度为偶数，且前半段与后半段完全相同的字符串。 要求找到替换后，字符串中能出现的最长串联重复子串的长度，无法构造则输出 $0$。

---

核心思路

1. 关键性质

一段长度为 $2d$ 的子串可以被改成串联重复串，当且仅当： 对于每一对位置 $i$ 和 $i+d$，两个字符相等，或至少有一个是问号。

2. 优化枚举方式

直接枚举所有子串会达到 $O(n^3)$，会超时。 正确做法是：

• 先枚举半段长度 $d$
• 再用滑动窗口统计合法匹配的数量
• 窗口右移时只需要 $O(1)$ 更新计数

3. 滑动窗口规则

对于固定的 $d$：

• 初始统计前 $d$ 对字符的可匹配数量 $cnt$
• 窗口右移一位时：
  • 去掉最左侧一对的贡献
  • 加入新进入的右侧一对的贡献
• 若 $cnt=d$，说明当前长度为 $2d$ 的子串合法

---

算法流程

1. 初始化答案 $ans=0$。
2. 枚举半段长度 $d$，从 $1$ 到 $\dfrac{n}{2}$。
3. 对每个 $d$，先计算初始窗口的合法匹配对数 $cnt$。
4. 向右滑动窗口，动态维护 $cnt$。
5. 若某一时刻 $cnt=d$，用 $2d$ 更新答案。
6. 遍历结束后输出 $ans$。

---

公式与复杂度分析

可匹配条件：

$$s[i] = s[i+d] \ \ \text{或} \ \ s[i]=\,? \ \ \text{或} \ \ s[i+d]=\,? $$

合法判定条件：

$$cnt = d \implies \text{存在长度为 } 2d \text{ 的串联重复串}$$

复杂度

每组测试用例时间复杂度：$O(n^2)$。 总字符串长度限制 $\sum n \le 5000$，因此总运算量约 $2.5\times 10^7$，可轻松通过时限。