如何计算非常大的网格中一个单词的数量？

Question

基本上有一个非常大的字母网格，只包含字母a，b和c：

aaaAAAaabbbbbbbbccccccc // a8 b8 c7
aaaBBBbbbbbbbbbbbbbcccc // a3 b16 c4
cccCCCbbbbaaaaaabbbbb // c6 b4 a5 b5

给出字母网格，找到垂直对齐的“ abc”数。约束列数为[1 ... 1,000,000,000]，行数为[1 ... 1,000]

输入：

3 23 <- number of rows, number of column
3 a 8 b 8 c 7 
3 a 3 b 16 c 4
4 c 6 b 4 a 5 b 5 <- number of letter groups, number of a, number of b, number of c where adjacent same letters are called letter groups

输出：

3

第二输入示例：

3 1000000
2 a 900000 b 100000 // aaaaaaa... ...aaaaAAAAAAA... ...bbbbbbbb
2 a 750000 b 250000 // aaaaaaa... ...aaaaBBBBBBB... ...bbbbbbbb
2 a 250000 c 750000 // aaaaaaa... ...ccccCCCCCCC... ...ccccccccc

输出：

150000

我还没有想出任何解决方案。任何人都有关于这个问题的线索吗？我应该使用哪种方法解决此类问题？它是动态编程吗？

Answer 1

如果输入的大小与其表示的网格相比较小（因为组的大小相对较大），则

not