Sofia and Strings
题面
\(t\) 组数据。
每一次测试，有长度为 \(n\) 的序列 \(s\)，长度为 \(m\) 的序列 \(t\)。
你可以对 \(s\) 进行两种操作：
-
删除 \(s_i,1\le i\le |s|\)（\(s\) 从 \(1\) 开始标号）.
-
将 \(s_l,s_{l+1},\dots,s_r\) 排序（\(1\le l\le r\le|s|\)）。
上面 \(|s|\) 是 \(s\) 的长度。
判断 \(s\) 是否可以变成 \(t\)，输出 YES 或者 NO。
\(1\le t\le10^4,1\le\Sigma n,\Sigma m\le2\times10^5\)。
做法
开一个二维pos数组，pos[a]这个数组中存的是所有a的下标。
处理完上面这一步后，我们再对t遍历，首先处理出t中所有有序的段，然后对于有序的段的字母数量，我们在其对应的pos中从小到大删去相应数量的下标，并且记录这里面下标的最大值，下一次删下标的时候，必须都要大于这个最大值。当数量不够的时候，就是no了。
这个做法很对，因为对于t中有序的段，我们可以通过s的子段排序后得到，但对于段与段之间，我们就只能去删，并不能排序，所以此时我们只能乖乖地从pos中按大小取了。
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,m;cin>>n>>m;
string a,b;cin>>a>>b;
deque<int>pos[30];
for(int i=0;i<n;i++)pos[a[i]-'a'].push_back(i);
int flag=0;
for(auto &i:b){
if(pos[i-'a'].empty()){
cout<<"NO\n";return ;
}
int temp=pos[i-'a'].front();
pos[i-'a'].pop_front();
for(int j=0;j<i-'a';j++){
while(!pos[j].empty()&&pos[j].front()<temp)
pos[j].pop_front();
}
}
cout<<"YES\n";
}
signed main(){
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
srand((unsigned)time(NULL));
int t;std::cin>>t;while(t--)
solve();
}