1363F Rotating Substrings

· · 个人记录

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

我们考虑类似 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 往后走一步。如果不是两两对应，还能是什么呢？