题解

思路

把未知串的每个位置视为变量。

做法

要求 $SS'$ 与 $S'S$ 回文，等价于分别把这两个连接串中关于中心对称的位置设为相同字符；约束可能连接两个变量，也可能把变量固定为 $S$ 中的某个字符。用并查集合并这些等价关系，并在每个连通块中记录它被固定到哪些字符，只要某个连通块同时包含两个不同字符就无解，否则可以任取字符补全所有未固定变量。

还需处理极大的 $K$。沿上述对称关系继续追踪未知位置时，每跨过 $2N$ 个位置，变量与 $S$ 中字符的对应关系会完整重复一次，因此可行性只与 $K\bmod 2N$ 有关；余数为零也按长度为零建立约束。令 $k=K\bmod 2N$ 后只需建立 $k+26$ 个并查集结点，并扫描两个长度为 $N+k$ 的连接串各一半。

复杂度

总时间复杂度为 $O(N\alpha(N))$，空间复杂度为 $O(N)$。