UOJ Logo Sharp Sword 剑锋 OI

SSOI

统计

时间限制:1S / 空间限制:256MB

【问题描述】

给定两个字符串t和p,设字符串t的长度为t_len。给定一个有1到t_len的数字组成的排列a,我们按照这个排列的顺序依次删除字符串t中对应位置的字符。
请问最多删除多个字符,使得字符串t依然包含字符串p。
输入数据保证,将t中的若干字符删除后包含字符串p。

例如t = "nastya" , a = [4, 1, 5, 3, 2, 6] ,依次删除的过程为:"nastya" "nastya" "nastya" "nastya" "nastya" "nastya" 。

请问最多删除多个字符,是的字符串t依然包含字符串p。输入数据保证,将t中的若干字符删除后包含字符串p。

【输入格式】

第一行一个字符串t,第二行一个字符串p,满足 (1 ≤ |p| < |t| ≤ 200 000),两条竖线表示字符串的长度;
第三行,|t|个整数,由1到|t|的整数组成的排列,每个数都不同。

【输出格式】

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

【输入样例1】

ababcba
abb
5 3 4 1 7 6 2

【输出样例1】

3

【输入样例2】

bbbabb
bb
1 6 3 4 2 5

【输出样例2】

4

【数据范围】

对于30%的数据,1 ≤ |p|< |t| ≤ 200;
对于50%的数据,1 ≤ |p| <|t| ≤ 2000;
对于80%的数据,1 ≤ |p| <|t| ≤ 20000;
对于100%的数据,1 ≤ |p| < |t| ≤ 200000;