AcWing 159. 奶牛矩阵    原题链接    中等

作者： 作者的头像   黄亦玫 ,  2020-10-21 11:33:31 ,  所有人可见 ,  阅读 498

2


算法思路

  • 先对行进行处理找到满足行的最小循环节，再对列做KMP即可。时间nm^2
    • 怎么找到满足所有行的最小循环结？
      • 如果所有行都满足完美循环节，那么只需要对每一行做一遍KMP找到每一行的最小循环节，再求一个最小公倍数即可。时间nm
      • 如果不满足的话，只能暴力枚举每一行的宽度，找到满足所有循环节的最小宽度nm^2
    • 接下来找到最小高度，那么对于每一个宽度我们看成一个字符即可，做一遍简单的KMP就行啦~~

0 评论