# Pattern Search in Grid

## 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

1. 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.
2. We only need to test the grid G for N-n columns, for the same reason as as in point 1.
3. 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.