题意：给定一个子串，询问一些子区间内的最短循环节(循环节是越短条件约束越多)
开始一看那就哈希处理然后暴力枚举循环节，然后按照循环节长度暴力向后比较，本地测试40，洛谷60
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int N=;
typedef unsigned long long ull; char s[N];int q;
ull p[N],sum[N],b; inline ull get(int l,int r){
return sum[r]-sum[l-]*p[r-l+];} int main(){
// freopen("2795.in","r",stdin);
// freopen("2795.out","w",stdout);
int n;scanf("%d",&n);
scanf("%s",s+); p[]=;b=; rep(i,,n) p[i]=p[i-]*b;
rep(i,,n) sum[i]=sum[i-]*b+(s[i]-'a'+); scanf("%d",&q);
rep(i,,q){
int l,r;scanf("%d%d",&l,&r);
int len=r-l+;
rep(j,,len){
if(len%j) continue;
int FG=;ull s=get(l,l+j-);
int k=(int)s;
for(int k=l+j;k<=r;k+=j)
if(s!=get(k,k+j-)){FG=;break;}
if(FG){printf("%d\n",j);break;}
}
}
return ;
}
再然后就是小作修改，在比较时计算新串哈希值，和原串比较，复杂度还是qn 2,不过本地47，洛谷60没变
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int N=;
typedef unsigned long long ull; char s[N];int q;
ull p[N],sum[N],b; inline ull get(int l,int r){
return sum[r]-sum[l-]*p[r-l+];} int main(){
// freopen("2795.in","r",stdin);
// freopen("2795.out","w",stdout);
int n;scanf("%d",&n);
scanf("%s",s+); p[]=;b=; rep(i,,n) p[i]=p[i-]*b;
rep(i,,n) sum[i]=sum[i-]*b+(s[i]-'a'+); scanf("%d",&q);
rep(i,,q){
int l,r;scanf("%d%d",&l,&r);
int len=r-l+,FG=;
ull s=get(l,r); rep(j,,len){
if(len%j) continue;
int cnt=len/j;
ull sk=get(l,l+j-),ss=; rep(k,,cnt)
ss+=sk*p[(cnt-k)*j];
if(ss==s) {printf("%d\n",j);FG=;break;}
}
if(FG) printf("0\n");
}
return ;
}
翻看题解之后明白了性质，总结如下
1.循环节是长度的约数，循环节越短限制条件越多
2.若n是循环节，k*n也是循环节
3.循环节判断方法，设循环节长度为k，[l,r-k]==[l+k,r]即相同
4.不断枚举质因数，实质上等同于枚举其约数，约数就是由质因数组成
5.一个合数，在欧拉筛过程中被筛掉时实际上由较大的质因数筛掉，所以若取被谁筛掉时应是较大质因数(说不定就是最大呢，可是我也不知道啊)
经过简单修改得到了在洛谷和bz上A掉的代码，但是本地测试78，还是有测试点没过，啊啊啊本地数据真的玄学
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int N=;
typedef unsigned long long ull; char s[N];int q,cnt,yueshu[N];
ull p[N],sum[N],b; inline ull get(int l,int r){//写成函数，真香
return sum[r]-sum[l-]*p[r-l+];}
int v[N],prime[N>>],nxt[N];
bool check(int l1,int r1,int l2,int r2){
if(get(l1,r1)==get(l2,r2)) return ;return ;}
void init(int n){
v[]=;
for(int i=;i<=n;i++){
if(!v[i]) prime[++cnt]=i,nxt[i]=i;
for(int j=;j<=cnt&&i*prime[j]<=n;j++){
v[i*prime[j]]=;
nxt[i*prime[j]]=prime[j];//nxt数组存储某个约数的质因数(应该是比较大的那个吧，菜鸡也只是猜的)
if(i%prime[j]==) break;}
}
}
int main(){
// freopen("2795.in","r",stdin);
// freopen("2795.out","w",stdout);
int n;scanf("%d",&n);
scanf("%s",s+);init(n); p[]=;b=; rep(i,,n) p[i]=p[i-]*b;
rep(i,,n) sum[i]=sum[i-]*b+(s[i]-'a'+); scanf("%d",&q);
rep(i,,q){
int l,r;scanf("%d%d",&l,&r);
int len=r-l+,idx=;
//nxt数组存储质因数
//yueshu数组内存储的是可以认为是未来的循环节个数
//e.g:10 5 2 存在多个质数
while(len!=){
yueshu[++idx]=nxt[len];//提前将可能除到1的质因数按照大小搞出来，这样就可以1个循环搞定
len=len/nxt[len];}
len=r-l+;
for(int j=;j<=idx;j++){
int k=len/yueshu[j];//得到的k才是循环节长度
if(check(l,r-k,l+k,r)) len=k;}
printf("%d\n",len);}
return ;
}
核心操作：判断长度的约数是不是循环节，删除后再继续判断
本来需要多层循环，但由于质因数的存在使得其实就是不断往下判断即可
啊啊啊，哈希kmpac自动机trie树继续刷题啊啊啊啊