Решение задачи Хеширование перемешиванием с Codeforces

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


Поликарп недавно создал новый веб сервис. Как в любом современном сервисе, в нем есть возможность авторизации. А это автоматически подразумевает угрозы безопасности.

Поликарп решил сохранять хеш пароля, полученный по следующему алгоритму:

получить пароль p, состоящий из строчных латинских букв, и перемешать буквы в нем, чтобы получить p′ (p′ может остаться равным p);
построить две случайные строки, состоящие из строчных латинских букв, s1 и s2 (любая из них может быть пустой);
полученный хеш h=s1+p′+s2, где сложение — это склеивание строк.
Например, пусть пароль будет p= «abacaba». Тогда p′ может быть равно «aabcaab». Случайные строки s1= «zyx» и s2= «kjh». Тогда h= «zyxaabcaabkjh».

Обратите внимание, что нельзя удалять или добавлять буквы в p, чтобы получить p′, можно только менять их порядок.

Теперь Поликарп просит вас помочь ему в реализации модуля проверки пароля. По данному паролю p и хешу h, проверьте, что h может являться хешом пароля p.

Вам нужно ответить на t наборов входных данных.

Код

#include<bits/stdc++.h>
using namespace std;
string s,t,b;
int T;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>s>>t;
		sort(s.begin(),s.end());
		int ok=0;
		if(s.size()<=t.size())
		for(int i=0;i<=t.size()-s.size();i++)
		{
			b=t.substr(i,s.size());
			sort(b.begin(),b.end());
			if(b==s) ok=1;
		}
		if(ok) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
} 

         

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



Комментарии

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