How to find all units a 2d grid of characters is made of?

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

What’s the effective algorithm to find all sizes of the same units one row of letters wide that all 2d grid of characters is constructed from? Our grid and units may consist of all lowercase letters of the English alphabet. Our unit can be in horizontal or vertical position. The first line of output should contain a number of units k and next k rows. Each row contains the size of unit. Any suggestions or help would be greatly appreciated.

Example:

in:

8 6
abaaab
aabbaa
bbabbb
aababa
bababb
aaabab
bbabaa
ababbb

out:

1
2

(Our grid can be constructed from one unit of size 2 –> "ab"):

Example image

But in case:

in:

4 5
aaaaa
aadaa
aaaaa
aaaaa

out:

0

(we don’t have any such units)

Source: Windows Questions C++

LEAVE A COMMENT