串联重复的兼容字符对

思路推导

先固定重复子串的半长 $d$。其前后两半对应位置的字符必须能够变得相同。两个字符兼容，当且仅当它们已经相同，或者至少一个是问号。

一个长度为 $2d$ 的候选子串中，每个位置只属于一对对应字符，因此这些兼容条件彼此独立：只要所有 $d$ 对字符都兼容，就能完成替换；如果有一对不同的已知字母，就不可能完成替换。

做法

枚举半长 $d$，从左到右检查所有相隔 $d$ 的字符对。维护当前连续兼容的字符对数量，遇到不兼容的字符对时清零。一旦连续数量达到 $d$，就找到了长度为 $2d$ 的可行子串。

按半长从大到小枚举，可以在第一次找到可行子串时直接返回它的长度。若所有半长均不可行，答案就是 $0$。

正确性证明

固定半长 $d$，任何长度为 $2d$、起点为 $l$ 的子串，恰好对应比较序列中从 $l$ 开始的 $d$ 对字符。根据兼容条件，这个子串可行当且仅当这连续 $d$ 对字符全部兼容。连续计数扫描恰好检测所有这样的区间，因此不会漏掉任何可行子串，也不会接受不可行子串。

算法按半长递减枚举。第一次找到的可行长度就是所有可行长度中的最大值；如果不存在任何可行长度，则正确输出 $0$。

复杂度

对每个半长进行一次线性扫描，总时间为 $O(n^2)$，其中 $n=|s|$。除存储输入字符串外，额外空间为 $O(1)$。多组测试的总长度受题面约束限制。

部分分思路

极小规模可以枚举每个问号的替换，然后枚举所有偶长子串。只需枚举原字符串出现过的字母；原串没有已知字母时枚举字母 a 即可。这不会漏掉最优值，因为每个待相等字符对要么受到某个已知字母约束，要么可以任选一个已有字母。枚举完成后的字符串再按字面检查，得到与兼容扫描独立的核验方式。

中等规模可以枚举起点和半长，逐字符检查前后两半，直接得到 $O(n^3)$ 的做法。

若不含问号，可以对每个后缀计算 Z 函数：当该后缀的 $z[d]\ge d$ 时，其开头存在长度为 $2d$ 的串联重复。这一方案也是 $O(n^2)$ 时间，但使用精确相等与 Z 区间复用；问号兼容关系不具传递性，不能直接把 Z 函数的字符相等替换为兼容判断。满分扫描用固定距离上的连续兼容状态处理一般情形。