KMP

KMP는 어떤 문자열이 다른 문자열의 부분 문자열로 등장하는 위치를 찾는 문자열 알고리즘이다. 알고리즘의 이름은 저자 세 사람, Donald Knuth, James Hiram Morris, Vaughan Pratt의 성의 첫 글자에서 따왔다.

이 문제는 그 알고리즘과는 관계가 없고, 이름을 붙이는 방식 자체에 관한 문제다. 이 세계에는 1번부터 N번까지 번호가 붙은 N명의 컴퓨터 과학자가 있다. i번째 컴퓨터 과학자의 이름은 $A_i$이다. 이름은 하나 이상의 단어로 이루어지며 단어 사이는 공백 하나로 구분된다. 단어는 하나 이상의 문자로 이루어지고, 첫 문자는 알파벳 대문자(A-Z), 나머지 문자는 알파벳 소문자(a-z)이다.

Q개의 질의가 주어지고, 각 질의는 대문자 알파벳으로 이루어진 문자열 S이다. 알고리즘 S가 이 N명의 컴퓨터 과학자의 부분집합에 의해 만들어질 수 있는지 판별해야 한다. 예를 들어 Donald Knuth, James Hiram Morris, Vaughan Pratt가 또 다른 알고리즘을 발명했다고 하자. 각 컴퓨터 과학자 이름에 등장하는 모든 단어의 첫 문자는 Donald Knuth의 경우 {D, K}, James Hiram Morris의 경우 {J, H, M}, Vaughan Pratt의 경우 {V, P}이다. 그러면 각 이름에서 첫 문자를 정확히 하나씩 골라 알고리즘 이름을 만들 수 있다(이때 고르는 대상은 N명 중 해당 부분집합이다). 예를 들어 DJV, DHP, KHV, KMP, KJP 등이 가능하다. 순서는 상관없으므로 PKH나 VHK 같은 이름도 유효하다. 하지만 이 예에서 KKMP나 LHO는 유효하지 않다.

더 형식적으로는 다음 조건을 만족하는 정수열 $X_1, X_2, \cdots, X_{|S|}$가 존재하는지 판별하는 것이다.

• $1 \le X_1, X_2, \cdots, X_{|S|} \le N$
• $i \ne j$이면 $X_i \ne X_j$
• $A_{X_i}$의 단어 중 하나가 문자 $S_i$로 시작한다

입력은 두 정수 N Q로 시작한다(1 ≤ N ≤ 50, 1 ≤ Q ≤ 1000). N은 컴퓨터 과학자의 수, Q는 질의의 수이다. 다음 줄에는 N개의 문자열 $A_i$가 주어지며, i번째 컴퓨터 과학자의 이름이다. 모든 $A_i$의 길이 합은 106 이하임이 보장된다. 다음 Q개의 줄에는 답을 구해야 하는 질의 문자열 S가 주어진다. 모든 S의 길이 합은 106 이하임이 보장된다. 또한 $A_i$와 S는 문제에서 제시한 형식을 만족함이 보장된다.

각 질의마다, 이름이 S인 알고리즘을 N명의 컴퓨터 과학자의 부분집합이 만들 수 있으면 한 줄에 “YES”를, 그렇지 않으면 “NO”를 출력한다.