[NOI Online 2022 普及组] 字符串题解

[NOI Online 2022 普及组] 字符串（暂无数据） - 洛谷

看到题目发现一个明显的问题，就是如果删除了一个前缀我们就去世了，但是我们最后的答案总是字符串 $T$ ，那么我们会考虑倒着做。

考虑怎么样才是可能合法的，也就是 $| S | - | T | - 减号的数量 \times 2$ 。

我们在这种情况下考虑 $D p$ ，设 $f (i, j)$ 表示 $T$ 的后缀 $j \sim m$ 匹配了 $S$ 中 $i \sim n$ 的一个合法子序列的方案数，之后考虑删除一个字符，我们发现如果选择删除后缀那么删除的肯定是下一个第一个不是减号的字符，我们需要记录这个删除的次数，再设一个 $K$ 。

因为可能有很多个减号连在一起。

$s_{i} = -$ ：

删除后缀 $f (i, j, k) \to f (i - 1, j, k + 1)$ 。
删除前缀 $f (i, j, k) \to f (i - 1, j, k)$ ，这里为什么不用操作，事实上我们考虑了所有的后缀删除然后如果 $T$ 已经是合法的，根据我们上述的条件剩下的删除操作都是在删前缀，而且前缀的长度恰好是符合要求的。

$s_{i} = 0 / 1$ ：

如果 $k > 0$ ， $f (i, j, k) \to f (i - 1, j, k - 1)$ 。
如果 $k = 0 \cap s_{i - 1} = t_{j - 1}$ ， $f (i, j, 0) \to f (i - 1, j - 1, 0)$ 。
如果 $k = 0, j = 1$ ，也就是我们已经完全匹配了，那么前面其实没有限制只需乘上前面的所有方案就行了，所以需要继承。 $f (i, 1, 0) \to f (i - 1, 1, 0)$ 。