IUPC and Password
Time limit0.5sMemory limit1024 MB
Given a base string S, decide for each query string T whether T can be formed by permuting S, then inserting arbitrary prefix and suffix strings, then changing exactly one character to a different one.
- Level
Medium7 of 10
- Topics
- String, Dynamic programming, Sliding window, Hash map
- Solved
- No attempts yet
Problem
Chihun is writing problems for IUPC (Inha University Ppakcoding Contest), a programming contest at Inha University.
The problems for the contest are top secret, so Chihun has set a password on the computer where they are stored. He creates the password as follows.
- Prepare a string (S) consisting only of lowercase English letters.
- Randomly shuffle the positions of the characters in the string.
- Append an arbitrary string to the front and another to the back of the shuffled string. The length of each appended string may be 0.
- Finally, choose one character at an arbitrary position and change it to a different character.
One day, while solving string problems, Chihun accidentally mixed the computer password together with other strings, and now he cannot tell which string was the password.
Chihun now has (N) candidate password strings. For the successful hosting of IUPC, determine whether each candidate password string could be the password!
Input
The first line gives (S).
The second line gives the number of candidate password strings, (N).
The next (N) lines give the (i)-th candidate password string (T_i), one per line.
Output
Over (N) lines, output whether each (T_i) could be the password.
Output "YES" if it could be, and "NO" if it could not.
Constraints
- 1 ≤ length of (S) ≤ 2,000
- 1 ≤ (N) ≤ 2,000
- 1 ≤ length of (T_i) ≤ 2,000
- All strings in the input consist only of lowercase English letters.