16590번 - KMP 다국어

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 i^th computer scientist has a name A_i. 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 X₁, X₂, · · · , X_|S| such that:

• 1 ≤ X₁, X₂, · · · , X_|S| ≤ N
• X_i ≠ X_j for i ≠ j
• One of the word in A_Xi starts with the character S_i

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: A_i representing the name of the i^th computer scientist. It is guaranteed that the sum of the length of all A_i is not more than 10⁶. 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 10⁶. 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”.