Решение задачи От S к T с Codeforces

Без пояснения   Просмотров: 24


У вас есть три строки s, t и p, состоящие из строчных букв латинского алфавита. Вы можете выполнять любое количество (возможно, нулевое) операций над этими строками.

Каждая операция выглядит следующим образом: вы выбираете любой символ из строки p, удаляете его из p и вставляете в любую позицию строки s (вы можете вставить этот символ куда захотите: в начало s, в конец или между любыми двумя подряд идущими символами).

Например, если p — это aba, и s — это de, тогда возможны следующие варианты (символ, удаленный из p и вставленный в s, выделен жирным шрифтом):

a ba → ba, de → a de;
a ba → ba, de → d a e;
a ba → ba, de → de a;
a b a → aa, de → b de;
a b a → aa, de → d b e;
a b a → aa, de → de b;
ab a → ab, de → a de;
ab a → ab, de → d a e;
ab a → ab, de → de a;
Вам нужно выполнить несколько (возможно, ноль) операций так, чтобы строка s стала равна строке t. Определите, возможно ли это.

Обратите внимание, что вам нужно ответить на q независимых запросов.

Код

#include <bits/stdc++.h>
using namespace std;
int mp[30];
string s,t,p;
void solve(){
	memset(mp,0,sizeof(mp));
	cin>>s>>t>>p;
	int j = 0;bool z = 0;
	for(int i=0;i<s.size();i++) mp[s[i]-'a']--;
	for(int i=0;i<t.size();i++){
		if(t[i] == s[j]) j++;
		if(j == s.size()) z = 1;
		mp[t[i]-'a']++;
	}
	if(z == 0){puts("NO");return;}
	for(int i=0;i<p.size();i++) mp[p[i]-'a']--;
	for(int i=0;i<t.size();i++){
		if(mp[t[i]-'a'] > 0){
			puts("NO"); return;
		}
	}
	puts("YES");
}
int main(){
	int t; scanf("%d",&t);
	while(t--) solve();
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться