아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

문자열 집합 판별

시간 제한1초메모리 제한256 MB

요약
패턴 집합과 질의 문자열이 주어지면 각 질의에 패턴과 일치하는 연속 부분 문자열이 있으면 YES를, 없으면 NO를 출력합니다.
난이도

보통10점 중 6점

유형
문자열 매칭, 트라이
정답자
아직 제출이 없습니다

문제

집합 SS는 크기가 NN이고, 원소가 모두 문자열이다. 문자열 QQ개가 주어졌을 때, 각 문자열의 부분 문자열 중 하나라도 SS에 있는지 판별하는 프로그램을 작성하시오. 하나라도 SS에 있으면 YES를, 하나도 없으면 NO를 출력한다. 여기서 부분 문자열은 문자열에서 연속한 구간을 뜻한다.

예를 들어 SS가 {"www", "woo", "jun"}인 경우를 보자. "myungwoo"는 부분 문자열 "woo"가 SS에 있으므로 답이 YES이고, "hongjun"은 부분 문자열 "jun"이 SS에 있으므로 답이 YES이다. 반면 "dooho"는 어떤 부분 문자열도 SS에 없으므로 답이 NO이다.

입력

첫째 줄에 집합 SS의 크기 NN이 주어진다. (1≤N≤10001 \le N \le 1000)

다음 NN개 줄에 걸쳐 SS의 원소가 한 줄에 하나씩 주어진다. 각 원소의 길이는 100100을 넘지 않는다.

다음 줄에 판별해야 하는 문자열의 개수 QQ가 주어진다. (1≤Q≤10001 \le Q \le 1000)

다음 QQ개 줄에 걸쳐 판별해야 하는 문자열이 한 줄에 하나씩 주어진다. 각 문자열의 길이는 1000010000을 넘지 않는다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 이루어져 있다.

출력

QQ개 줄에 걸쳐 각 문자열의 답을 입력에 주어진 순서대로 출력한다. 부분 문자열 중 하나라도 SS에 있으면 YES를, 하나도 없으면 NO를 출력한다.

예제1

  1. 예제 1

    입력
    3
    www
    woo
    jun
    3
    myungwoo
    hongjun
    dooho
    
    예상 출력
    YES
    YES
    NO