The Grid Search

Given a 2D array of digits or grid, try to find the occurrence of a given 2D pattern of digits. For example, consider the following grid:

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  

Assume we need to look for the following 2D pattern array:

876543  
111111  
111111

The 2D pattern begins at the second row and the third column of the grid. The pattern is said to be present in the grid.

Function Description

Complete the gridSearch function in the editor below. It should return YES if the pattern exists in the grid, or NO otherwise.

gridSearch has the following parameter(s):

• G: the grid to search, an array of strings
• P: the pattern to search for, an array of strings

Input Format

The first line contains an integer , the number of test cases.

Each of the  test cases is represented as follows:
The first line contains two space-separated integers  and , indicating the number of rows and columns in the grid .
This is followed by  lines, each with a string of  digits representing the grid .
The following line contains two space-separated integers,  and , indicating the number of rows and columns in the pattern grid .
This is followed by  lines, each with a string of  digits representing the pattern .

Constraints

Output Format

Display YES or NO, depending on whether  is present in .

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

Sample Output

YES
NO

Explanation

The first test in the input file is:

10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530

As one may see, the given pattern is present in the larger grid, as marked in bold below.

7283455864  
6731158619  
8988242643  
3830589324  
2229505813  
5633845374  
6473530293  
7053106601  
0834282956  
4607924137  

The second test in the input file is:

15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

The search pattern is:

99
99

This cannot be found in the larger grid.

 php

<?php

// Complete the gridSearch function below.

function getFirstRow($G, $P) {

$ar = array();

$frstln = $P[0];

$lst = strlen($G[0]) - strlen($P[0]);

foreach($G as $k => $g) {

if(strpos($g, $frstln) !== false) {

$star = strpos($g, $frstln);

for( $i = $star ; $i <= $lst; $i++ ) {

$mtch = substr($g, $i, strlen($frstln));

if($mtch == $frstln) {

$ar[] = array('row' => $k, 'fst' => $i);

}

}

}

}

return $ar;

}

function gridSearch($G, $P) {

$ar = getFirstRow($G, $P);

$lnp = count($P);

$ln = strlen($P[0]);

foreach($ar as $r) {

$rw = $r['row'];

$fst = $r['fst'];

$arr = array();

for($i = $rw ; $i < $rw+$lnp; $i++) {

$arr[] = substr($G[$i], $fst, $ln);

}

if($arr == $P) {

return 'YES';

}

}

return 'NO';

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%d\n", $t);

for ($t_itr = 0; $t_itr < $t; $t_itr++) {

fscanf($stdin, "%[^\n]", $RC_temp);

$RC = explode(' ', $RC_temp);

$R = intval($RC[0]);

$C = intval($RC[1]);

$G = array();

for ($i = 0; $i < $R; $i++) {

$G_item = '';

fscanf($stdin, "%[^\n]", $G_item);

$G[] = $G_item;

}

fscanf($stdin, "%[^\n]", $rc_temp);

$rc = explode(' ', $rc_temp);

$r = intval($rc[0]);

$c = intval($rc[1]);

$P = array();

for ($i = 0; $i < $r; $i++) {

$P_item = '';

fscanf($stdin, "%[^\n]", $P_item);

$P[] = $P_item;

}

$result = gridSearch($G, $P);

fwrite($fptr, $result . "\n");

}

fclose($stdin);

fclose($fptr);