10152: SPOJ ARDA1 - The hunt for Gollum
[Creator : ]
Description
Along the skirts of the Dead Marshes I followed it, and then I had him. Lurking by a stagnant mere, peering in the water as the dark eve fell, I caught him, Gollum. He was covered with green slime. He will never love me, I fear; for he bit me, and I was not gentle. Nothing more did I ever get from his mouth than the marks of his teeth.
ription. If none match is found, you should output the string “NO MATCH FOUND...” without the quotes.
“The Lord of the Rings: The fellowship of the Ring”
Hearing Gandalf’s advice, Aragorn has started hunting creature Gollum. After several days following his footprints, he has arrived to the Dead Marshes. He has a map of the marshes, that can be viewed as an $M_1 \times M_2$ matrix containing lowercase letters form English alphabet (i.e. letters from ‘a’ to ‘z’).
Being a skilled ranger, Aragorn has been able to fully characterize Gollum preferred place (if you are interested, you should know that it must be dark, wet, creepy and full of fishes!). It can be described as an $N_1 \times N_2$ matrix containing lowercase letters form English alphabet.
Your task is simple: write a program that, given Gollum’s preferred place description and Aragorn’s map, output all possible locations of the creature.
Let’s look at an example: suppose Gollum’s preferred place is described by the following $3 \times 3$ matrix:
- aba
- bab
- aba
- aababa
- ababab
- bababa
- ababab
- ababab
- bababa
- ababab
Input
Line 1: Two integers: $N_1, N_2$.
Lines $2… N_1 + 1$: A string with $N_2$ characters as described above.
Lines $N_1 + 2$: Two integers: $M_1, M_2$.
Lines $N_1 + 3… N_1 + M_1 + 3$: A string with $M_2$ characters as described above.
Lines $2… N_1 + 1$: A string with $N_2$ characters as described above.
Lines $N_1 + 2$: Two integers: $M_1, M_2$.
Lines $N_1 + 3… N_1 + M_1 + 3$: A string with $M_2$ characters as described above.
Output
On each line print the upper-left corner of all places that match Gollum’s preferred place description on the form “$(x,y)$” without the quotes, where $x$ stands for the row and $y$ for the column. They should be lexicographically sorted, i.e. imagine them as an ordered pair. Then $(x_1, y_1) < (x_2, y_2)$ if and only if $x_1 < x_2$ or, if they are equal, $y_1 < y_2$.
Constraints
$1 ≤ N_1, N_2 ≤ 300$
$1 ≤ M_1 * M_2 ≤ 2000$
$N_1 ≤ M_1$
$N_2 ≤ M_2$
$1 ≤ M_1 * M_2 ≤ 2000$
$N_1 ≤ M_1$
$N_2 ≤ M_2$
Sample 1 Input
3 3
aba
bab
aba
7 6
aababa
ababab
bababa
ababab
ababab
bababa
ababab
Sample 1 Output
(1,2)
(1,4)
(2,1)
(2,3)
(5,1)
(5,3)