A Horrible Poem-字符串哈希+线性筛

本文主要是介绍A Horrible Poem-字符串哈希+线性筛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A Horrible Poem-字符串哈希+线性筛

题目描述

题解

首先明确几个性质
1，循环节的长度必为该区间 $S [a . . . b]$ 长度的约数—显而易见
2，当 $S [a . . . b - l e n] = = S [a + l e n . . . b]$ 时， $S [x . . . y]$ 必为 $S [a . . . b]$ 的循环节；( $l e n$ 为 $S [x . . . y]$ 的长度)
证明可以自己手玩，这是我们判断循环节的重要根据
根据这2条性质，算法显而易见，枚举 $l$ 的约数( $l$ 为 $S [a . . . b]$ 的长度),然后哈希判断是否为循环节，但该题卡 $O (n \sqrt n)$ ,因此线性筛横空而出，首先预处理-线性筛，维护出每个数的最小质因数，然后比如找 $l$ 的质因数时就递归思想，继续找 $l / v [l]$ 的质因数，( $v [i]$ 表示 $i$ 的最小质因数)

代码

#include<bits/stdc++.h>//字符串哈希判循环节 
#define M 500009
#define LL unsigned long long
using namespace std;
int n,q,v[M],p[M],t[M],cnt;
LL has[M],mi[M];
char s[M];
const int h=31;
int read(){int f=1,re=0;char ch;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());if(ch=='-'){ch=getchar();f=-1;}for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';return re*f;
}
void init(){for(int i=2;i<=n;i++){if(!v[i]){v[i]=i;p[++cnt]=i;}for(int j=1;j<=cnt;j++){if(p[j]*i>n||v[i]<p[j]) break;v[p[j]*i]=p[j];}}cnt=0;
}
LL gethas(int l,int r){return has[r]-has[l-1]*mi[r-l+1];
}
int main(){n=read(),init();scanf("%s",s+1),mi[0]=1;for(int i=1;i<=n;i++){has[i]=has[i-1]*h+(s[i]-'a');mi[i]=mi[i-1]*h;}q=read();for(int i=1;i<=q;i++){int l=read(),r=read();int len=r-l+1;cnt=0;while(len!=1){t[++cnt]=v[len];len=len/v[len];//依次找len的质因数 }len=r-l+1; for(int j=1;j<=cnt;j++){//逐渐缩小长度 int ans=len/t[j];if(gethas(l,r-ans)==gethas(l+ans,r)) len=ans;}printf("%d\n",len);}return 0;
}