题意:
题解:对于有排序操作且不限次数,最好考虑每次只对两个排序,如果t中的字母在s中的j位置,则s[0,j]之间小于t中字母的字母都要消去,用队列存s中字母的位置,扫描t,每次用s中剩余位置最小的,在消去不可用的即可。
代码:
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pll;
typedef tuple<int,int,int> TP;
const int N = 1e6 + 10;
void solve()
{
int n,m;
string s,t;
cin>>n>>m;
cin>>s>>t;
queue<int> q[30];
for(int i=0;i<n;i++)
{
int w=s[i]-'a';
q[w].push(i);
}
for(int i=0;i<m;i++)
{
int w=t[i]-'a';
if(q[w].empty())
{
cout<<"NO\n";
return ;
}
int d=q[w].front();
q[w].pop();
// cout<<d<<" "<<" "<<w<<" "<<t[i]<<"\n";
for(int j=0;j<w;j++)
{
while(q[j].size()&&q[j].front()<d)
{
q[j].pop();
}
}
}
cout<<"YES\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0 ^ 0;
}