What’s the number of templates lengths which we can print all our grid of letters? [closed]

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

We have to print a 2d grid written in text. The grid may consist of all lowercase letters of the English alphabet. All letters are placed on the grid with dimensions n * m. We can make a printout using a printing template – his width is one row of letters. Printing will take place by potentially repeatedly applying the printing template and splashing the ink exactly over the stencil. The template mustn’t extend beyond the grid. The template will be prepared in a horizontal and a vertical version – both versions must contain the same text. We have to print each element of our grid using the template exactly once. None of the template versions can be rotated that letters don’t print rotated. We want to print all template lengths we can use to print a whole grid. The first line of output should contain a single integer – the number of templates lengths which we can print all our grid. The second line should contain all these lengths.

Example:

in:

8 6
abaaab
aabbaa
bbabbb
aababa
bababb
aaabab
bbabaa
ababbb

out:

1
2

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

Example image

But in case:

in:

4 6
aaaaaa
aahaaa
aaaaaa
aaaaaa

out:

0

(we don’t have any such templates)*

Source: Windows Questions C++

LEAVE A COMMENT