시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 83 | 23 | 20 | 30.769% |
KMP is a string algorithm that searches for occurrences of a string as substrings on another string. The name of the algorithm comes from the first character of the last names of the authors, namely Donald Knuth, James Hiram Morris, and Vaughan Pratt.
This problem has nothing to do with the algorithm, rather this problem is about the naming itself. There are N computer scientists in this world numbered from 1 to N. The ith computer scientist has a name Ai. A name consists of one or more word, separated by a single space. A word consists of one or more characters. The first character is an uppercase alphabetical character (A-Z), while the rest of the characters are lowercase alphabetical characters (a-z).
There are Q queries, each consists of a string S of uppercase alphabetical characters. You are wondering whether an algorithm S can be authored by a subset of these N computer scientists. Let say Donald Knuth, James Hiram Morris, and Vaughan Pratt invent another algorithm. The first characters of any word in each computer scientist’s name are {D, K} in Donald Knuth, {J, H, M} in James Hiram Morris, and {V, P} in Vaughan Pratt. Then the algorithm can be named by taking exactly one of those first characters from each name (in the subset of the N computer scientists), e.g., DJV, DHP, KHV, KMP, KJP, etc. Note that the order does not matter, so algorithm names like PKH or VHK are also valid. However, KKMP or LHO are not valid in this example.
More formally, you are wondering whether there is a sequence of integers X1, X2, · · · , X|S| such that:
Input begins with two integers: N Q (1 ≤ N ≤ 50; 1 ≤ Q ≤ 1000) representing the number of computer scientists and the number of queries, respectively. The next line contains N strings: Ai representing the name of the ith computer scientist. It is guaranteed that the sum of the length of all Ai is not more than 106. The next Q lines contains a string S representing the query which you should answer. It is guaranteed that the sum of the length of all S is not more than 106. It is also guaranteed that Ai and S satisfy the format given in the problem statement.
For each query, output “YES” in a line if an algorithm of name S can be authored by a subset of the N computer scientists; otherwise, output “NO”.
3 3 Donald Knuth Vaughan Pratt James Hiram Morris KMP DVJ LHO
YES YES NO
The sample input/output illustrates the example given in the problem statement above.
3 3 Donald Knuth Vaughan Pratt James Hiram Morris D KP KKMP
YES YES NO
Note that you can choose a subset of the N computer scientists.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2018 F번