CF778A String Game

小娜斯佳有一个爱好，她喜欢从一个单词中删除一些字母，以得到另一个单词。但这对她来说很难，因为她还太小。因此，她的哥哥谢尔盖总是会帮助她。 谢尔盖给了娜斯佳一个单词 $t$，并希望从中得到单词 $p$。娜斯佳会按照一定顺序（严格按顺序一一删除）删除字母，这个顺序由单词 $t$ 的字母下标的一个排列 $a_1...\ a_{|t|}$ 指定。我们用 $|x|$ 表示单词 $x$ 的长度。注意，删除某个字母后，其他字母的下标不会变化。例如，如果 $t=\text{nastya}$ 且 $a=[4,1,5,3,2,6]$，那么删除后得到的单词序列如下：“nastya”（下同）。 谢尔盖知道这个排列。他的目标是在某个时刻让娜斯佳停下来，然后由自己继续删除字母来得到单词 $p$。由于娜斯佳喜欢这样做，谢尔盖希望让她尽可能晚地停下。你的任务是确定娜斯佳最多可以删除多少个字母。 保证通过删去 $t$ 的若干字母可以得到 $p$。

输入的第一、第二行分别包含单词 $t$ 和 $p$。单词由小写拉丁字母组成（$1 \leq |p| < |t| \leq 200000$）。保证通过删除 $t$ 中的一些字母可以得到 $p$。 下一行包含一个排列 $a_1,a_2,\ldots,a_{|t|}$，表示娜斯佳删除 $t$ 的字母的顺序（$1 \leq a_i \leq |t|$，且所有 $a_i$ 均不同）。

输出一个整数，表示娜斯佳最多可以删除的字母数。

在第一个样例中，娜斯佳的删除顺序如下： "ababcba"（下同） 娜斯佳不能继续删除，因为此时无法从 "ababcba" 得到单词 "abb"。 因此，娜斯佳最多只能删除三个字母。 由 ChatGPT 5 翻译