레이저
시간 제한5초메모리 제한128 MB
격자를 순환 인덱싱해서 만든 무한 문자열에 각 단어가 부분 문자열로 나타나는, max(a,b) <= K인 서로소 방향 벡터의 개수를 구하는 문제입니다.
문제
2차원 평면의 정수 좌표 (x, y)는 문자 하나에 대응된다. 이 문자는 g[y % R][x % C]이다. 여기서 R은 배열 g의 행 수, C는 열 수이며, g의 크기는 R x C이다.
원점 (0, 0)에서 레이저 광선을 쏜다. 광선이 x와 y가 모두 0 이상인 정수 좌표들을 지날 때, 그 좌표의 문자들을 원점에서 가까운 순서대로 이어 붙이면 무한한 문자열이 된다.
서로 다른 광선은 서로 다른 방향의 기하학적 광선이다. 광선은 적어도 하나의 0이 아닌 정수 좌표 (x, y)를 지나야 하며, 이 좌표는 0 <= x <= K, 0 <= y <= K를 만족해야 한다.
단어가 하나 주어졌을 때, 어떤 광선의 무한 문자열이 그 단어를 부분 문자열로 포함하면 그 광선은 그 단어를 만든다고 한다. 주어진 각 단어를 만드는 서로 다른 광선의 개수를 구하라.
입력
첫째 줄에 배열 g의 크기 R과 C가 주어진다. R과 C는 35 이하의 자연수이다.
다음 R개의 줄에는 배열 g의 각 행이 주어진다. 모든 문자는 알파벳 소문자이다.
그다음 줄에 단어의 개수 N이 주어진다. N은 25 이하의 자연수이다.
다음 N개의 줄에는 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있으며 길이는 최대 50이다.
마지막 줄에 K가 주어진다. K는 200 이하의 자연수이다.
출력
입력된 단어마다 그 단어를 만드는 레이저 광선의 개수를 구해, 입력 순서대로 공백으로 구분하여 출력한다.
힌트
K = 2이고 배열이 abc / def / ghi일 때 가능한 방향의 문자열은 abcabc..., afhafh..., aeiaei..., ahfahf..., adgadg...의 다섯 가지이다.