错位比较 发表于 2018-10-29 分类于 ACM ， 学习笔记 ， 字符串 阅读次数： 本文字数： 320 阅读时长 ≈ 1 分钟 nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial codeforces 1043B 本质上让你求一个字符串可能的循环节，题目的第二个样例可以看作求序列 1，2，2，1，2，的循环节显然可以是3或5， 于是算法出来了，我们只要求出最小的循环节就可以了，最小的循环节怎么来求呢，我们hash预处理原字符串以便后面O1查询区间hash值，对于字符串s如下图，我们对原字符串复制一份，错位比较红色竖线之间的子串，如果相等，意味着什么读者可以自行思考，于是我们已经找到了On的做法了，我们只要从小到大枚举 蓝色区域即可
)