题解：CF778A String Game

删除字母的个数显然越多越好，再看题目中的 Note that after removing one letter, the indices of other letters don't change. 这句话，意思是删除一个字母后，其他字母的索引不会更改。因此可以二分可以删除的字母的个数，最后输出最大值。

首先确定二分的范围，由数据范围可知，$p$ 串最少删除的字母数量为 $0$。又因为再删除若干个字母后的长度一定不比 $t$ 串的长度小，那么设两个串的长度分别为 $lenp,lent$，则最多删除的字母数量为 $lenp - lent$。

其次再来思考删除字母后判断 $p$ 串中是否仍存在 $t$ 串的方式。先计算出被删除若干个字母的新 $p$ 串，然后利用两个指针 $dx,dy$，分别表示新 $p$ 串与 $t$ 串的匹配状态。通过 while 循环，逐一判断，显然能成功匹配的条件是 $dy = lent$，即表示 $t$ 串中的所有字母都在新 $p$ 串中按顺序出现。

通过二分答案，大大地减少了搜索的次数，时间复杂度也变为 $O(n \log n)$，$n$ 表示 $p$ 串的长度。完整代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int lena,lenb,cnt,num[MAX];
char a[MAX],b[MAX],str[MAX];
bool del[MAX];
bool check (int x);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    scanf ("%s%s",a,b);
    lena = strlen (a);lenb = strlen (b);
    for (int i = 1;i <= lena;++i) num[i] = read ();
    int l = 0,r = lena - lenb;//确定范围
    while (l <= r)//二分答案
    {
        int mid = (l + r) >> 1;
        if (check (mid)) l = mid + 1;
        else r = mid - 1;
    }
    printf ("%d\n",l - 1);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
bool check (int x)
{
    for (int i = 1;i <= lena;++i) del[i] = 0;//初始化
    for (int i = 1;i <= x;++i) del[num[i]] = 1;//删除的字母的下标标记为 1
    cnt = 0;
    for (int i = 0;i < lena;++i)
        if (!del[i + 1]) str[++cnt] = a[i];//构成新字符串 p
    int dx = 1,dy = 0;
    while (dx <= cnt && dy < lenb)//循环逐一比较
    {
        if (str[dx] == b[dy]) ++dx,++dy;
        else ++dx;
    }
    if (dy != lenb) return 0;//没有完全匹配
    else return 1;//能完全匹配
}