考虑把插入字符变成从 $t$ 里面删除字符。设 $f(i,j)$ 表示经过 $i$ 次操作，其中 $t$ 做的删除操作比 $s$ 做的删除操作多 $j$ 个，能让 $s$ 和 $t$ 多长的前缀相同（即最大的 $x$ 满足 $s[1:x]$ 和 $t[1:x+j]$ 的编辑距离不超过 $i$）。转移需要求 $s[x:]$ 和 $t[y:]$ 的 LCP，二分哈希即可。时间复杂度 $O(n+m+k^2\log(n+m))$。