시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 31 | 8 | 5 | 71.429% |
영선이는 야매 점술사이다. 영선이는 아주 간단한 방법으로 점을 봐서, 운의 양을 결정한다. n x m 격자판에 각 칸마다 알파벳이 쓰여 있다. 그리고 점을 보러온 사람이 k길이의 단어를 임의로 작성한다. 그러면 영선이는 그 단어의 연속된 일부분이 최대한 일치하게 격자판의 문자와 겹치게 만들고, 그 길이를 통하여 운의 양을 결정한다. 겹치게 만들 때는 가로나 세로에 평행하게 두며, 문자의 순서는 위,아래,왼쪽,오른쪽 4방향 중 어느 방향이여도 상관없다. 또한, 일치하지 않은 문자는 격자판을 벗어나도 상관없다.
예를 들어 아래와 같은 상황에서 AHMRVP 라는 단어를 찾는다면, (2,3) 부터 (4,3)까지 연속된 일부분인 HMR을 겹치게 둘 수 있다.
그리고 JEHGFP의 경우도 (2,3)부터 (2,1)까지 연속된 일부분인 HGF를 찾을 수 있다. ,
영선이는 야매 점술사인데 반해, 우연을 통하여 점괘를 잘 맞추기 때문에 의외로 인기가 많다. 오늘도 p명의 사람의 점괘를 봐줘야 한다. 하지만 영선이는 점괘로 번 돈으로 놀고 있기 때문에, 영선이를 대신하여 각 단어별로 격자판에서 단어를 찾아주자.
첫쨰줄에는 점괘를 보는 격자판의 크기 n,m이 주어진다.(1≤n,m≤100)
다음 n줄에는 격자판의 문자 m개가 주어진다.
다음줄에는 점괘를 보러 온 사람의 수 p, 단어의 길이 k가 주어진다. (1≤p≤100,000 , 1≤k≤30)
다음 p줄에는 점괘를 보러 온 사람이 적은 단어의 문자 k개가 주어진다.
점괘에 사용되는 모든 문자는 알파벳 대문자를 사용한다.
각 단어별로 가장 긴 연속된 일부분 문자의 길이를 출력하시오.
5 5 ABCDE FGHIJ KLMNO PQRST UVWXY 3 6 AHMRVP JEHGFP ZZZZZZ
3 3 0