题目内容

公司里有两个字符串，分别是 $s$ 和 $t$ 。由于数据安全的原因,字符串 $t$ 不允许作为 $s$ 的子串存在。为了满足数据规范，米小游需要按照一定的顺序删除字符串 $s$ 中的一些字符，确保 $s$ 中不再包含 $t$ 。注意删除字符 $s_i$ 后，不会自动将前后字符串合并，你可以认为使用一个空白字符代替 $s_i$ 。

米小游想知道，在保证 $s$ 不包含 $t$ 的前提下，她最少需要删除多少个字符？

删除顺序可以描述为一个排列，$a_i$ 表示删除 $s_{a_i}$ 字符。

题解

题面描述

给定两个字符串 $s$（长度 $n$）和 $t$（长度 $m$），为了数据安全，需要删除 $s$ 中的字符，使得 $t$ 不再作为 $s$ 的子串（即连续片段）出现。删除顺序由长度为 $n$ 的排列 $a$ 给出，表示第 $i$ 次删除位置为 $a_i$（删除后用空白字符替代，不会合并剩余字符）。

请问最少需要删除多少个字符，才能保证删除后的 $s$ 中不包含 $t$ 作为子串？

思路