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

Pattern Search in Grid
Pattern Search in Grid

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.

Source Code

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)