题库练习 净化传输信号
← 上一题 下一题 →

A6964 | 净化传输信号

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

通信卫星接收到了一串长度为 $N$ 的原始信号字符串 source
经过初步分析,我们识别出了其中包含的一段核心指令字符串 patternpattern 保证是 source 的子序列)。

为了优化存储空间,系统标记了一组“冗余下标” targetIndices
你可以对 source 进行“清理操作”:
1. 每次操作可以删除 source 中下标位于 targetIndices 中的任意一个字符。
2. 删除操作后,剩余的字符串必须仍然包含 pattern 作为其子序列(字符顺序不变)。
3. 操作不改变字符在原始字符串中的相对下标判定(即下标是固定的,不会因为前面的字符被删除了而改变后续字符的下标索引)。

请问:在保证 pattern 完整性的前提下,你**最多**可以执行多少次删除操作?

输入格式

输入共三部分:
1. 第一行包含一个字符串 source
2. 第二行包含一个字符串 pattern
3. 第三行包含一个整数 $K$,表示可删除下标数组的长度。
4. 第四行包含 $K$ 个整数,表示 targetIndices 的元素,保证按升序排列且互不相同。

输出格式

输出一个整数,表示最多可以删除的字符数量。

输入输出样例

输入 #1
abbaa
aba
3
0 1 2
输出 #1
1
输入 #2
bcda
d
2
0 3
输出 #2
2
C++ 编辑器
输入
输出