题解

题面描述

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

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

思路

题目内容

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

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

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

输入描述

第一行输入两个整数 $n$ 和 $m$ ，表示字符串 $s$ 和 $t$ 的长度。

第二行输入一个长度为 $n$ 的字符串 $s$ ，仅包含小写字母。

第三行输入一个长度为 $m$ 的字符串 $t$ ，仅包含小写字母。

第四行输入一个长度为 $n$ 的排列 $a$，表示第 $i$ 次删除 $s_{a_i}$ 字符。

$1≤n≤ 10^5$

$1≤m≤50$

$1 ≤a_i ≤n$

输出描述

输出一个整数，表示最少需要删除的字符个数。

样例1

输入

5 2
ababa
ab
3 2 5 4 1

输出

2

说明

第一次删除 $S_3$ ，$s$ 变为 ab a ba。

第二次删除 $S_2$ ，$s$ 变为 a ba ba。

此时 $s$ 不包含 $t$ ，最少需要删除 $2$ 个字符。