CF2196E：SA的应用

首先贪心的思路是显然的，因此我们相当于在t串中不断求最长可错配lcp

法1：根号分治

我们考虑以 $B$ 分块

• Case1：对于 $d\le B$ 的情况。（即一次最多走 $d$ 步）

我们可以先预处理 $s$ 中所有小于等于 $B$ 的子串，并枚举它的哪个位置是空的。接下来把这个串挖掉这个空直接丢入hash中（相当于我们枚举的这一位直接赋值为0），这样的复杂度是 $O(nB^2)$ 的。

然后我们现在处理 $t$ 串。我们可以枚举每一个被替换的位置 $i$ ，那么显然 $i$ 只有 $B$ 种可能。然后我们再去枚举 $d$。

但枚举 $d$ 的这个过程可以优化。假设对于一个 $i$，如果 $d+1$ 可以，那么 $d$ 一定可以。因此我们可以维护当前最长 的 $d_{mx}$，在 $i$ 不断右移的过程中，去试试 $d_{mx}+1$ 是否可行（因为更短的就没必要了）。在这种情况下，$i$ 和 $d$ 构成了two-pointer，因此一次枚举的复杂度就是 $O(B)$ 的。因此这一部分的复杂度是 $O(mB)$。

• Case2：对于 $d>B$ 的情况

在这种情况下，我们可以直接枚举 $s$ 串的开头 $j$（显然要枚举 $n$ 次）。然后对于每个 $s[j:n]$，我们让其与 $t[l:m]$ 取一次LCP（这个可以SA+RMQ预处理），然后跳过LCP+1的位置，再取一次LCP，就可以求出它们两个的最长长度了。这样一次的复杂度是 $O(n)$ 的。

而我们只有在Case1中发现 $d$ 至少可以取到 $B$，我们才会进入这一轮的判断。因此只要进入了这一轮的判断，至少会走 $\frac m B$ 步。因此这部分的复杂度是 $O(\frac{nm}B)$ 的。

因此这种做法的总复杂度是 $O(nB^2+mB+\frac{nm}B)$，可以取 $B=50$，可以通过easy version

法2：SA + 二分

首先我们通过预处理SA，可以对于当前的 $t[l:m]$，在 $O(1)$ 的时间内找到与 $s$ 所有后缀的LCP的最大值。

接下来有一个比较明显的性质：我们修改的这个位置，一定在小于等于这个最长LCP+1。

因为我们可以枚举这个修改的位置。枚举的总次数是 $O(m)$ 的，因为这一轮我们至少会走LCP步。

枚举完修改位置，我们也可以直接枚举成替换成哪个字母。不妨假设在 $ps$ 位置进行修改，修改完后待匹配的串是 $t'$。（注意这个 $t'$ 是从 $l$ 位置开始的）

接下来我们想要寻找的是 $t'$ 和 $s$ 所有后缀的最长LCP。

去找这个最长LCP，我们可以在 $s$ 串自己的后缀数组中，找到满足 $s_j\le t'\le s_k$，然后分别求 $j,k$ 与 $t'$ 的LCP即可。

对于找 $j,k$ 的过程，我们可以采用二分的办法。以找 $j$ 为例，我们直接二分。然后求原串 $t$ 和当前 $s_j$ 的LCP，不妨设为 $q$。

• 若 $ps\le q$，我们可以直接比较出 $t'$ 与 $s_j$ 的大小关系（在 $ps$ 位比较一下即可）
• 若 $ps > q+1$，我们也可以直接比较二者的大小关系（$t'$ 和 $t$ 在这种情况下等价）
• 若 $ps=q+1$，我们可以再求一次 $s[j+q+1:n]$ 和 $t[l+q+1:m]$ 的LCP，这也是 $O(1)$ 的。

因此，我们可以在 $\log$ 的时间内求出 $j,k$。同时，在上面的过程中，我们其实已经实现了求LCP的过程了。

总复杂度 $O(26m\log n)$