What’s the effective algorithm for finding all sizes of patterns you can fill all 2d grid of characters with

  2d, algorithm, c++, pattern-matching

What would be an effective algorithm for searching through 2D grid of characters size nm and check if we can fill all our grid with a pattern of size 1k which has a constant sequence of characters? Our grid and pattern may consist of all lowercase letters of the English alphabet. We can "place" our pattern on our grid horizontally and vertically. I want to find all sizes of "stamps" which cover all our grid. Every character on our grid can be filled only once. If we don’t have any such patterns, the final result is 0. I have an idea to use KMP 2d searching algorithm. Otherwise are there any similar articles/books on the subject? Any suggestions or help would greatly appreciated.

Example:

in:

8 6

abaaab

aabbaa

bbabbb

aababa

bababb

aaabab

bbabaa

ababbb

out:

1

2

(We can fill our grid with a one pattern only – size 1 * 2. We can fill all our grid with a pattern "ab".)

But in case:

in:

4 5

aaaaa

aadaa

aaaaa

aaaaa

out:

0

(we don’t have any 1 * k such patterns)

Source: Windows Questions C++

LEAVE A COMMENT