숨은 단어 찾기
시간 제한1초메모리 제한256 MB
아는 단어 목록과 각 메시지가 주어질 때 메시지 안에 부분 문자열로 들어 있는 단어를 세어 없으면 NO, 하나면 그 단어, 둘이상이면 AMBIGUOUS를 출력합니다.
문제
흰 토끼는 검은 토끼에게 단어 하나를 보내려고 한다. 다른 토끼가 그 단어를 알아채면 안 되기 때문에, 흰 토끼는 검은 토끼와 미리 약속을 해 두고 자기가 아는 단어를 모두 알려 주었다. 단어를 보낼 때는 그 단어의 앞뒤와 사이에 다른 글자를 잔뜩 섞어 긴 메시지 하나로 만들어 보낸다.
메시지를 하나 받으면, 흰 토끼가 아는 단어 중에서 그 메시지 안에 연속한 부분 문자열로 나타나는 단어를 모두 찾는다. 이렇게 찾은 서로 다른 단어가 정확히 하나면 그것이 흰 토끼가 보내려던 단어다. 검은 토끼를 도와 메시지마다 답을 구하라.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다 (). 각 테스트 케이스는 다음과 같이 이루어진다.
- 첫째 줄에 흰 토끼가 아는 단어의 개수 이 주어진다 ().
- 다음 개 줄에 흰 토끼가 아는 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이 는 6 이상 50 이하이고, 단어는 알파벳 소문자로만 이루어진다.
- 그다음 줄에 흰 토끼가 보낸 메시지의 개수 이 주어진다 ().
- 다음 개 줄에 메시지가 한 줄에 하나씩 주어진다. 각 메시지의 길이 는 6 이상 10000 이하이고, 메시지는 알파벳 소문자로만 이루어진다.
출력
메시지마다 한 줄씩 답을 출력한다. 먼저 그 메시지 안에 연속한 부분 문자열로 나타나는, 흰 토끼가 아는 서로 다른 단어의 개수를 센다.
- 그런 단어가 하나도 없으면 NO를 출력한다.
- 정확히 하나면 그 단어를 그대로 출력한다.
- 둘 이상이면 AMBIGUOUS를 출력한다.