哈希UVALive 6326 Contest Hall Preparation
2024-09-25 22:24:51
Encrypting passwords is one of the most important problems nowadays, and you trust only the encryp-
tion algorithms which you invented, and you have just made a new encryption algorithm.
Given a password which consists of only lower case English letters, your algorithm encrypts this
password using the following 3 steps (in this given order):
1.
Swap two different characters of the given password (you can do this step zero or more times).
2.
Append zero or more lower case English letters at the beginning of the output of step one.
3.
Append zero or more lower case English letters to the end of the output of step two.
And the encrypted password is the output of step three.
You have just nished implementing the above algorithm and applied it on many passwords. Now
you want to make sure that there are no bugs in your implementation, so you decided to write another
program which validates the output of the encryption program. Given the encrypted password and the
original password, your job is to check whether the encrypted password may be the result of applying
your algorithm on the original password or not.
Input
Your program will be tested on one or more test cases. The rst line of the input will be a single
integer
T
, the number of test cases (1
T
100). Followed by the test cases, each test case is on two
lines. The rst line of each test case contains the encrypted password. The second line of each test case
contains the original password. Both the encrypted password and the original password are at least 1
and at most 100,000 lower case English letters (from `
a
' to `
z
'), and the length of the original password
is less than or equal the length of the encrypted password.
Output
For each test case, print on a single line one word, `
YES
' (without the quotes) if applying the algorithm on
the original password may generate the encrypted password, otherwise print `
NO
' (without the quotes).
SampleOutput
3
abcdef
ecd
cde
ecd
abcdef
fed
SampleOutput
YES
YES
NO//有坑
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int hash[maxn];
int cur[maxn];
char s[],t[];
int h[];
int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
memset(h,,sizeof(h));
memset(hash,,sizeof(hash));
memset(cur,,sizeof(cur));
memset(t,,sizeof(t));
memset(s,,sizeof(s));
scanf("%s",t);
getchar();
scanf("%s",s);
getchar();
int len1=strlen(s);
int len2=strlen(t); for(int i=; i<len1; i++)
{
int temp=s[i];
hash[temp]++;
} int ans=;
int cnt=;
bool flag=false;
if(len1==len2)
{
for(int i=; i<len2; i++)
{
int d=t[i];
h[i]=d;
if(cur[d]<hash[d])
cnt++;
cur[d]++;
if(cnt==len1){
flag=true;
break;
}
}
} else
{
for(int i=; i<len2; i++)
{ int d=t[i];
h[i]=d;
if(cur[d]<hash[d])
cnt++;
cur[d]++; if(i>=len1)
{
d=h[i-len1];
if(cur[d]<=hash[d])
cnt--;
cur[d]--; }
if(cnt==len1){
flag=true;
break;
} }
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return ;
}
最新文章
- Python开发入门与实战16-APACHE部署
- 在Github上注册账户
- python数据结构之二叉树的实现
- 剑指offer系列50--不用加减乘除做加法
- C#基础回顾以及if语句
- 基于AgileEAS.NET企业应用开发平台的分布式解决方案
- 关于Azure Auto Scale的高级属性配置
- C/C++各种系统开发环境搭建
- Portlet MVC框架
- Developer Tool - 1. Text Tool and GNU/Linux Tool
- sublime text3输出窗口中文显示乱码问题解决方案
- 查看log日志
- linux sort排序命令的高级用法(按多个列值进行排列)
- js控制全屏及退出全屏
- 从web到搭建ssm环境
- python闭包的详细解析
- jar包的读取1
- v-html对于↵转义的问题
- poj-2142-exgcd/解的和最小
- HttpClient-传入url得到json字符串( PostMethod method = new PostMethod(url)是个好方法)