错位比较

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

codeforces 1043B

本质上让你求一个字符串可能的循环节,题目的第二个样例可以看作求序列 1,2,2,1,2,的循环节显然可以是3或5, 于是算法出来了,我们只要求出最小的循环节就可以了,最小的循环节怎么来求呢,我们hash预处理原字符串以便后面O1查询区间hash值,对于字符串s如下图,我们对原字符串复制一份,错位比较红色竖线之间的子串,如果相等,意味着什么读者可以自行思考,于是我们已经找到了On的做法了,我们只要从小到大枚举 蓝色区域即可