本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 18:56:06

这个循环右移相当不常规吧，所以也很难用常规的状态去描述它。一般的状态没法描述循环右移导致的改变。

我们考虑类似 $f_{ij}$ 的状态，表示匹配到 $s$ 前 $i$ 个字符，$t$ 的前 $j$ 个，所需要的最少的操作数量。

首先有朴素的转移 $f_{i-1j-1} + 1$，当 $s_i = t_j$。

然后，我们可以不让 $i$ 和 $j$ 匹配，而是把 $i$ 塞到前头和某个位置匹配，即 $f_{i-1j} + 1$。

同时，对应着“往前塞”的转移，我们可以也必须有一个“往后放”的转移。不这样的化，往前塞的转移是转移不到 $f_{00}$ 的。这条转移是 $f_{ij} = f_{ij-1}$。

我们想一想这个为啥是正确的。也就是：每一个往前塞的转移，是否都对应前面一个往后放的转移。

这是必须的。因为我们只能从 $(0, 0)$ 出发转移，且只有第一种转移是 $x, y$ 同时加一的；往前塞的转移，会让 $y$ 相对 $x$ 往前移动一步，往后放的转移会让 $y$ 相对 $x$ 往后走一步。如果不是两两对应，还能是什么呢？