ARDA1 - The hunt for Gollum

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.

“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 M1 × M2 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 N1 × N2 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 × 3 matrix:

  • aba
  • bab
  • aba

and that Aragorn’s map looks something like this:

  • aababa
  • ababab
  • bababa
  • ababab
  • ababab
  • bababa
  • ababab

Then your program must output the following: (1,2), (1,4), (2,1), (2,3), (5,1) and (5,3), these being the upper-left corners of all places on the Dead Marshes that match Gollum’s preferred place description. If none match is found, you should output the string “NO MATCH FOUND...” without the quotes.

Input

Line 1: Two integers: N1 and N2.

Lines 2… N1 + 1: A string with N2 characters as described above.

Lines N1 + 2: Two integers: M1 and M2.

Lines N1 + 3… N1 + M1 + 3: A string with M2 characters as described above.

Constraints

1 ≤ N1, N2 ≤ 300

1 ≤ M1 * M2 ≤ 2000

N1 ≤ M1

N2 ≤ M2

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 (x1, y1) < (x2, y2) if and only if x1 < x2 or, if they are equal, y1 < y2.

Example

Input:
3 3
aba
bab
aba
7 6
aababa
ababab
bababa
ababab
ababab
bababa
ababab

Output:
(1,2)
(1,4)
(2,1)
(2,3)
(5,1)
(5,3)

Added by:Camilo Bravo Valdés
Date:2010-03-11
Time limit:0.405s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem

hide comments
2017-05-13 01:14:00 Sigma Kappa
I got Accepted with Aho-Corasick.
2016-09-29 17:54:10
cost me 7 WA because I copy paste "NO MATCH FOUND..." becasue the last dot didn't appear directly I don't know why most problems spoj make complex output or input !!!!

Last edit: 2016-09-29 17:58:27
2016-07-04 08:57:33
Go Brute Force, unless you've come here in the search of KMP problems. :)
2016-01-27 17:24:37
NAIVE SEARCH GIVES TLE.
2015-09-13 23:55:04 Garima
easy
1 WA because I forgot to print NO MATCH FOUND...
2015-06-13 21:13:04 Mateusz Wasylkiewicz
I think there should be "1 ≤ M1, M2 ≤ 2000" instead of "1 ≤ M1 * M2 ≤ 2000".
2014-12-28 00:00:30 triveni
Note: M1 * M2 is definitely greater than 200000 but less than 1000000.

To the Problem Setter : Don't you know that people chose to code a problem according the constraints given in the problem ? Based on the constraints we choose the algorithm which is easier to implement(or easy to think). Or don't you know how to set constraints ?

Complete waste of time !

Last edit: 2014-12-28 00:02:19
2014-12-21 09:57:31 Swapnil Borse
Cake Walk!!! 0.20 sec in C
one WA because of NO MATCH FOUND.. instead of NO MATCH FOUND...
A word of caution, directly copy paste the string from the sample test cases whenever it is to be printed so that is doesn't cost an unnecessary wrong answer!!! :P :D
2013-09-08 10:06:44 Luka
NO MATCH FOUND...
2013-08-30 12:32:57 Shafaet
Constraint "1 ≤ M1 * M2 ≤ 2000" is not true. Thats pathetic problemsetting.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.