반지
면접 대비시간 제한1초메모리 제한128 MB
각각 10글자 원형 문자열인 N개의 고리 중에서 주어진 검색 문자열을 원을 따라 읽었을 때 포함하는 고리의 개수를 센다.
문제
당신은 개의 반지를 가지고 있습니다. 각 반지에는 대문자로 이루어진 길이 의 문자열이 새겨져 있습니다. 반지에 새겨진 문자열은 처음과 끝이 서로 이어져 있어 원형으로 읽힙니다. 문자열을 거꾸로 읽는 경우는 고려하지 않습니다.
찾고자 하는 문자열이 주어졌을 때, 그 문자열을 (원형으로 읽었을 때) 포함하는 반지가 몇 개인지 세는 프로그램을 작성하세요.
입력
첫 번째 줄에 찾고자 하는 문자열이 주어집니다. 이 문자열은 길이가 이상 이하이며 대문자로만 이루어져 있습니다.
두 번째 줄에 반지의 개수 ()이 주어집니다.
이어지는 개의 줄 중 번째 줄에는 번째 반지에 새겨진, 대문자 자로 이루어진 문자열이 주어집니다.
출력
찾고자 하는 문자열을 포함하는 반지의 개수를 정수 하나로 한 줄에 출력하세요.
힌트
반지의 문자열은 시작과 끝이 이어져 있으므로, 찾는 문자열이 문자열의 끝에서 시작해 처음으로 되돌아가며 나타날 수도 있습니다. 예를 들어 반지 ZAAAAAAAXY에는 문자열 XYZ가 원형으로 한 번 나타납니다(끝의 XY 다음에 처음의 Z가 이어집니다).
또한 한 반지 안에 찾는 문자열이 여러 번 나타나더라도, 그 반지는 한 개로만 셉니다. 예를 들어 PQRAAAAPQR에는 PQR가 두 번 나타나지만 반지 한 개로 셉니다.