本质上让你求一个字符串可能的循环节,题目的第二个样例可以看作求序列 1,2,2,1,2,的循环节显然可以是3或5, 于是算法出来了,我们只要求出最小的循环节就可以了,最小的循环节怎么来求呢,我们hash预处理原字符串以便后面O1查询区间hash值,对于字符串s如下图,我们对原字符串复制一份,错位比较红色竖线之间的子串,如果相等,意味着什么读者可以自行思考,于是我们已经找到了On的做法了,我们只要从小到大枚举 蓝色区域即可
- 本文作者: fightinggg
- 本文链接: http://fightinggg.github.io/yilia/yilia/PHCM3Z.html
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!