codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1278A.md (2387B)


      1 Source: https://codeforces.com/problemset/problem/1278/A
      2 
      3 A. Shuffle Hashing
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Polycarp has built his own web service. Being a modern web service it includes login feature. And that always implies password security problems.
     22 
     23 Polycarp decided to store the hash of the password, generated by the following algorithm:
     24 
     25 1. take the password $p$, consisting of lowercase Latin letters, and shuffle the letters randomly in it to obtain $p'$ ($p'$ can still be equal to $p$);
     26 2. generate two random strings, consisting of lowercase Latin letters, $s_1$ and $s_2$ (any of these strings can be empty);
     27 3. the resulting hash $h = s_1 + p' + s_2$, where addition is string concatenation.
     28 
     29 For example, let the password $p =$ "abacaba". Then $p'$ can be equal to "aabcaab". Random strings $s1 =$ "zyx" and $s2 =$ "kjh". Then $h =$ "zyxaabcaabkjh".
     30 
     31 Note that no letters could be deleted or added to $p$ to obtain $p'$, only the order could be changed.
     32 
     33 Now Polycarp asks you to help him to implement the password check module. Given the password $p$ and the hash $h$, check that $h$ can be the hash for the password $p$.
     34 
     35 Your program should answer $t$ independent test cases.
     36 
     37 Input
     38 
     39 The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.
     40 
     41 The first line of each test case contains a non-empty string $p$, consisting of lowercase Latin letters. The length of $p$ does not exceed $100$.
     42 
     43 The second line of each test case contains a non-empty string $h$, consisting of lowercase Latin letters. The length of $h$ does not exceed $100$.
     44 
     45 Output
     46 
     47 For each test case print the answer to it — "YES" if the given hash $h$ could be obtained from the given password $p$ or "NO" otherwise.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 abacaba
     56 zyxaabcaabkjh
     57 onetwothree
     58 threetwoone
     59 one
     60 zzonneyy
     61 one
     62 none
     63 twenty
     64 ten
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES
     71 YES
     72 NO
     73 YES
     74 NO
     75 ```
     76 
     77 Note
     78 
     79 The first test case is explained in the statement.
     80 
     81 In the second test case both $s_1$ and $s_2$ are empty and $p'=$ "threetwoone" is $p$ shuffled.
     82 
     83 In the third test case the hash could not be obtained from the password.
     84 
     85 In the fourth test case $s_1=$ "n", $s_2$ is empty and $p'=$ "one" is $p$ shuffled (even thought it stayed the same).
     86 
     87 In the fifth test case the hash could not be obtained from the password.