만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Reverse Severer

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

요약
문자열 S를 여러 조각으로 나눈 뒤 조각의 순서를 뒤집어 이어 붙여 각 질의 문자열 T를 만들 수 있는지 판별합니다.
난이도

보통10점 중 7점

유형
문자열, 동적 계획법, 문자열 매칭
정답자
아직 제출이 없습니다

문제

길이가 NN인 문자열 SS가 주어진다. 질의는 QQ개이며, 각 질의마다 아래 알고리즘을 초기 문자열 SS에 적용해서 길이가 NN인 문자열 TiT_i를 만들 수 있는지 판단해야 한다.

  1. 문자열 SS를 하나 이상의 부분 문자열로 나눈다.
  2. 부분 문자열들의 순서를 뒤집는다.
  3. 부분 문자열들을 이어 붙여 하나의 문자열로 만든다.

예를 들어, 문자열 REVERSE를 R, E, VER, SE로 나눌 수 있다. 부분 문자열의 순서를 뒤집으면 SE, VER, E, R이 되고, 이어 붙이면 SEVERER가 된다.

입력

첫 번째 줄에 정수 NN (1≤N≤10 0001 \le N \le 10\,000)이 주어진다.

두 번째 줄에 길이가 NN인 문자열 SS가 주어진다.

세 번째 줄에 정수 QQ (1≤Q≤1001 \le Q \le 100)가 주어진다.

이어지는 QQ개의 줄에 각각 길이가 NN인 문자열 TiT_i가 주어진다.

모든 문자열은 영어 대문자로만 이루어져 있다.

출력

각 질의마다 TiT_i를 위 알고리즘으로 얻을 수 있으면 YES, 없으면 NO를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    7
    REVERSE
    5
    SEVERER
    EVERSER
    REVERSE
    EVEREST
    RESERVE
    
    예상 출력
    YES
    YES
    YES
    NO
    NO
    
  2. 예제 2

    입력
    3
    INC
    6
    INC
    ICN
    NIC
    NCI
    CIN
    CNI
    
    예상 출력
    YES
    NO
    NO
    YES
    YES
    YES
    
  3. 예제 3

    입력
    1
    A
    2
    A
    B
    
    예상 출력
    YES
    NO