|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||1||1||1||100.000%|
You have a grid G containing R rows (numbered from 1 to R, top to bottom) and C columns (numbered from 1 to C, left to right) of uppercase characters. The character in the rth row and the cth column is denoted by Gr,c. You also have Q strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.
An occurrence of string S in the grid is counted if S can be constructed by starting at one of the cells in the grid, going right 0 or more times, and then going down 0 or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string S, you would like to count the number of tuples <r, c, ∆r, ∆c> such that:
Input begins with a line containing three integers: R C Q (1 ≤ R, C ≤ 500; 1 ≤ Q ≤ 200 000) representing the size of the grid and the number of strings, respectively. The next R lines each contains C uppercase characters representing the grid. The cth character on the rth line is Gr,c. The next Q lines each contains a string S containing uppercase characters. The length of this string is a positive integer not more than 200 000. The sum of the length of all Q strings combined is not more than 200 000.
For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.
3 3 5 ABC BCD DAB ABC BC BD AC A
2 3 1 0 2
2 3 3 AAA AAA A AAA AAAAA
6 4 0