시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 0 0 0 0.000%

문제

이차원 평면 상에 있는 점은 다음과 같은 규칙에 의해서 문자 하나와 대응시킬 수 있다.

(x, y)는 g[y%R][x%C]에 있는 문자와 대응된다. R은 배열의 행의 수이고, C는 열의 수이다. g는 2차원 배열이고, 크기는 R*C이다.

레이저를 (0, 0)에서 쏜다고 가정하자. 레이저가 x와 y가 모두 0보다 크거나 같은 정수 좌표를 지나갈 때, 지나간 순서대로 문자열을 만들 수 있다.

세준이는 단어를 N개 가지고 있다. 세준이는 각 단어를 부분문자열로 가지는 레이저 광선의 개수가 궁금해졌다. 단어를 부분문자열로 가진다는 말은 레이저가 지나간 순서대로 만든 길이가 무한인 문자열이 단어를 부분문자열로 포함하는 것이다.

또, 레이저는 적어도 하나의 (x, y) (0<=x<=k, 0<=y<=k, x와 y는 정수)를 지난다고 가정한다.

입력으로 주어지는 단어가 만들어지는 서로 다른 레이저 광선의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 g배열의 크기 R과 C가 주어진다. R과 C는 35보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 g배열에 있는 문자가 주어진다. 문자는 알파벳 소문자이다. 다음 줄에는 단어의 개수 N이 주어진다. 다음 줄부터 N개의 줄에는 단어가 한 줄에 하나씩 주어진다. N은 25보다 작거나 같은 자연수이며, 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 마지막 줄에 K가 주어진다. K는 200보다 작거나 같은 자연수이다.

출력

각 단어를 만드는 레이저 광선이 몇 개인지 입력 받은 순서대로 출력한다.

예제 입력

3 3
abc
def
ghi
1
abc
2

예제 출력

1

힌트

K=2일 때, 레이저 광선이 만들 수 있는 단어는 다음과 같이 5개이다. abcabc…… afhafh…… aeiaei…… ahfahf……. adgadg......

출처