枚举 border 长度

设字符串长度为 $n$。

若一个长度为 $b$ 的前缀同时也是后缀，那么等价于

$$S[1:b]=S[n-b+1:n]$$

令

$$d=n-b$$

那么要比较的其实是两段等长字符串：

• 左边：$S[1:b]$；
• 右边：$S[d+1:n]$。

因此可以枚举位移 $d=1,2,\dots,n-1$，对应的 border 长度就是 $b=n-d$。

对固定的 $d$，我们关心序列

$$S_1,S_2,\dots,S_b$$

和

$$S_{d+1},S_{d+2},\dots,S_n$$

在多少个位置上不同。

---

失配位置的分类

设这两段字符串中失配的位置为

$$p \iff S_p \ne S_{p+d}\qquad (1 \le p \le b)$$

由于一次询问只允许把某一个位置 $i$ 改成 $T_i$，所以：

• 如果失配位置至少有 $3$ 个，那么显然无解；
• 如果恰有 $1$ 个失配位置，那么只能修改这对失配字符中的某一个；
• 如果恰有 $2$ 个失配位置，那么只有当这两个失配“共用同一个原串位置”时，才可能通过修改这一个位置使它们同时消失。

下面分别讨论。

情况 1：没有失配

也就是原串 $S$ 本身就有这个 border。

此时如果修改的位置完全不参与这组比较，那么这个 border 一定仍然成立。

什么时候会“不参与比较”呢？

当两段区间没有重叠时，中间可能会有一段空白区间：

• 前缀部分覆盖位置 $[1,b]$；
• 后缀部分覆盖位置 $[d+1,n]$。

若 $b<d$，那么中间的

$$[b+1,d]$$

这些位置不属于前缀，也不属于后缀。修改这些位置不会影响这个 border。

---

情况 2：恰有一个失配

设唯一的失配位置为 $p$，即

$$S_p \ne S_{p+d}$$

若要修好它，只能改这两个位置之一。

但是还要注意：如果某个位置同时还参与了别的配对，那么改掉它可能会破坏别处。

因此只有下面两种情况可行：

• 修改左端点 $p$，要求它只出现在左串中，不再出现在右串中，也就是 $p<d$；同时还要满足

$$T_p=S_{p+d}$$

• 修改右端点 $p+d$，要求它只出现在右串中，不再出现在左串中，也就是 $p+2d>n$；同时还要满足

$$T_{p+d}=S_p$$

---

情况 3：恰有两个失配

设最左边的失配位置为 $p$，最右边的失配位置为 $q$，即

$$S_p \ne S_{p+d},\qquad S_q \ne S_{q+d},\qquad p<q$$

如果这两组失配涉及的四个位置互不相同，那么修改一个字符至多修掉其中一组，显然无解。

唯一可能有解的情况是：

$$q=p+d$$

此时两组失配分别是

$$(p,p+d),\qquad (p+d,p+2d)$$

它们共用中间位置 $p+d$。

这时只有修改中间位置 $p+d$ 才可能同时消除两处失配，并且必须满足

$$T_{p+d}=S_p=S_{p+2d}$$

---

如何在线性时间内判断失配个数

直接逐个比较所有 $d$ 的话是 $O(n^2)$，无法通过。

我们需要快速知道：

• 左边连续匹配了多长；
• 右边连续匹配了多长；
• 中间某一段是否完全相同。

用 Z 函数求最长前缀匹配

对原串 $S$ 求一遍 Z 函数。

对于固定的 $d$，z[d] 就表示

$$\operatorname{LCP}(S[1:n],S[d+1:n])$$

的长度。

因为当前只关心长度为 $b=n-d$ 的两段，所以真正有用的是

$$\min(z[d],b)。$$

这就是两段字符串从左往右连续相同了多少位。

用反串的 Z 函数求最长后缀匹配

将字符串反转得到 $R$，对 $R$ 再求一遍 Z 函数。

这样同样可以得到，对于固定的 $d$，两段字符串从右往左连续相同了多少位。

记：

• lcp 为左边连续匹配长度；
• lcs 为右边连续匹配长度。

那么：

• 若 lcp = b，说明没有失配；
• 若 lcp + lcs >= b-1，说明至多只有一个失配；
• 否则，至少有两个失配。

用哈希判断是否恰好只有两个失配

当 lcp + lcs < b-1 时，我们已经知道最左失配位置和最右失配位置之间至少留出了一段中间区间。

设：

• 最左失配位置为 $p$；
• 最右失配位置为 $q$。

如果中间这一段

$$(p,q)$$

完全匹配，那么失配就恰好只有两个；否则失配至少有三个。

这个“中间整段是否相等”的判断，可以用字符串哈希在 $O(1)$ 时间完成。

---

按 border 从大到小给答案

我们按

$$d=1,2,\dots,n-1$$

枚举，也就是按

$$b=n-1,n-2,\dots,1$$

从大到小枚举 border 长度。

因此对于每个位置 $i$，只要第一次发现它可以得到某个 border 长度 $b$，这个 $b$ 就一定是答案。

为了避免一个位置被重复处理，可以维护一个并查集（或 next 数组跳点）：

• 只把满足 $S_i \ne T_i$ 的位置加入；
• 一旦某个位置答案确定，就把它从集合中删除；
• 之后再遇到区间赋值时，直接跳到下一个还没确定的位置。

这样每个位置最多被删除一次，总复杂度仍然是线性的。

---

原串本身不变的位置

如果某个位置满足

$$S_i=T_i$$

那么这次“替换”实际上没有发生任何变化，得到的字符串仍然是原串 $S$。因此这些位置的答案，直接等于原串 $S$ 的最大 border，这个值在枚举过程中顺便维护即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。