【codeforces】1278A. Shuffle Hashing

2984 단어 # 문자열
Polycarp has built his own web service. Being a modern web service it includes login feature. And that always implies password security problems.
Polycarp decided to store the hash of the password, generated by the following algorithm:
  • take the password pp, consisting of lowercase Latin letters, and shuffle the letters randomly in it to obtain p′p′ (p′p′ can still be equal to pp);
  • generate two random strings, consisting of lowercase Latin letters, s1s1 and s2s2 (any of these strings can be empty);
  • the resulting hash h=s1+p′+s2h=s1+p′+s2, where addition is string concatenation.

  • For example, let the password p=p= “abacaba”. Then p′p′ can be equal to “aabcaab”. Random strings s1=s1= “zyx” and s2=s2= “kjh”. Then h=h= “zyxaabcaabkjh”.
    Note that no letters could be deleted or added to pp to obtain p′p′, only the order could be changed.
    Now Polycarp asks you to help him to implement the password check module. Given the password pp and the hash hh, check that hh can be the hash for the password pp.
    Your program should answer tt independent test cases.
    Input
    The first line contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.
    The first line of each test case contains a non-empty string pp, consisting of lowercase Latin letters. The length of pp does not exceed 100100.
    The second line of each test case contains a non-empty string hh, consisting of lowercase Latin letters. The length of hh does not exceed 100100.
    Output
    For each test case print the answer to it — “YES” if the given hash hh could be obtained from the given password pp or “NO” otherwise.
    Example
    input
    5
    abacaba
    zyxaabcaabkjh
    onetwothree
    threetwoone
    one
    zzonneyy
    one
    none
    twenty
    ten
    

    output
    YES
    YES
    NO
    YES
    NO
    

    Note
    The first test case is explained in the statement.
    In the second test case both s1s1 and s2s2 are empty and p′=p′= “threetwoone” is pp shuffled.
    In the third test case the hash could not be obtained from the password.
    In the fourth test case s1=s1= “n”, s2s2 is empty and p′=p′= “one” is pp shuffled (even thought it stayed the same).
    In the fifth test case the hash could not be obtained from the password.
    문제풀이
    직접 폭력
    코드
    #include
    #include
    #include
    using namespace std;
     
    char s1[105],s2[105];
     
    int main()
    {
        int t;
        cin>>t;
        getchar();
        while(t--){
            gets(s1);
            gets(s2);
            int len_1,len_2;
            len_1=strlen(s1);
            len_2=strlen(s2);
            sort(s1,s1+len_1);
            if(len_1>len_2){
                printf("NO
    "); continue; } bool flag; for(int i=0;i

    좋은 웹페이지 즐겨찾기