## Problem Statement

Given a huge grid **G** with **M** rows and **N** columns and a pattern **P** with **m** rows and **n** columns. The task at hand is to perform a pattern search in grid, and print **YES** if the pattern grid **P** exists in the grid **G **otherwise print** NO**

Its a simple string search but requires special attention to the boundary cases. Here is a list of them

- We only need to test the grid
**G**for**M-m**rows, because anything below row R-r cannot accommodate the pattern of size r. - We only need to test the grid
**G**for**N-n**columns, for the same reason as as in point 1. - There could be possibly more than one occurrence of the search string from P in any row of G. Therefore we need to test all possibilities in a row first.

## Algorithm

Here are the steps to follow to complete this program

- For a row I of grid G, find all indices of the first row of pattern P.
- If no indices found from the above step, move to the next row of G.
- If indices are found, for each index K from the above step, find if the rows 2 to r of P exists in the grid from rows I+1 to I+r – 1 and columns K+1 to K+c-1

- Repeat the above steps until we find the complete pattern at least once or we reach R-r rows.

## Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
boolean found = false; // test for each row of the grid G till R-r row, because anything below that can never accommodate the pattern P. for (int j = 0; j <= R - r; j++) { List<Integer> indices = new ArrayList<Integer>(); String g = G.get(j); int index = 0; while (index <= C - c) { index = g.indexOf(p, index); if (index == -1) break; indices.add(index++); } if (indices.size() > 0) { StringBuilder completeGrid = new StringBuilder(); for (Integer ind : indices) { for (int i = j; i < j + r; i++) { completeGrid.append(G.get(i).substring(ind, ind + c)); } if (completeGrid.toString().equals(completePattern.toString())) { res = "YES"; found = true; break; } } if (found) break; } } |

Github link: Grid Search Code

## Analysis

The algorithm takes at max O(C-c) space to store all the indices in one of the matching rows. Which means that the required space is O(N).

The running time required is for iterating through R-r rows and for each row testing all C-c columns. which means O(N*M) worst case. We need to add some constant work per index to match the complete grid.

The string search will take O(m*n) additional. Considering m and n are significantly smaller than M and N. we can safely ignore them as lower order terms.

In case M and N are pretty big, then R-r and C-c will approach 1 and hence this will always converge to the worst case running time of O(N*M)