반지

면접 대비

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

요약
각각 10글자 원형 문자열인 N개의 고리 중에서 주어진 검색 문자열을 원을 따라 읽었을 때 포함하는 고리의 개수를 센다.
난이도

쉬움10점 중 3점

유형
문자열, 문자열 매칭, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

당신은 NN개의 반지를 가지고 있습니다. 각 반지에는 대문자로 이루어진 길이 1010의 문자열이 새겨져 있습니다. 반지에 새겨진 문자열은 처음과 끝이 서로 이어져 있어 원형으로 읽힙니다. 문자열을 거꾸로 읽는 경우는 고려하지 않습니다.

찾고자 하는 문자열이 주어졌을 때, 그 문자열을 (원형으로 읽었을 때) 포함하는 반지가 몇 개인지 세는 프로그램을 작성하세요.

입력

첫 번째 줄에 찾고자 하는 문자열이 주어집니다. 이 문자열은 길이가 11 이상 1010 이하이며 대문자로만 이루어져 있습니다.

두 번째 줄에 반지의 개수 NN (1≤N≤1001 \le N \le 100)이 주어집니다.

이어지는 NN개의 줄 중 ii번째 줄에는 ii번째 반지에 새겨진, 대문자 1010자로 이루어진 문자열이 주어집니다.

출력

찾고자 하는 문자열을 포함하는 반지의 개수를 정수 하나로 한 줄에 출력하세요.

힌트

반지의 문자열은 시작과 끝이 이어져 있으므로, 찾는 문자열이 문자열의 끝에서 시작해 처음으로 되돌아가며 나타날 수도 있습니다. 예를 들어 반지 ZAAAAAAAXY에는 문자열 XYZ가 원형으로 한 번 나타납니다(끝의 XY 다음에 처음의 Z가 이어집니다).

또한 한 반지 안에 찾는 문자열이 여러 번 나타나더라도, 그 반지는 한 개로만 셉니다. 예를 들어 PQRAAAAPQR에는 PQR가 두 번 나타나지만 반지 한 개로 셉니다.

예제3

  1. 예제 1

    입력
    ABCD
    3
    ABCDXXXXXX
    YYYYABCDXX
    DCBAZZZZZZ
    
    예상 출력
    2
    
  2. 예제 2

    입력
    XYZ
    1
    ZAAAAAAAXY
    
    예상 출력
    1
    
  3. 예제 3

    입력
    PQR
    3
    PQRAAAAPQR
    BBPQRBBBBB
    CCCCCCCCCC
    
    예상 출력
    2