【题解】【P3538 [POI2012]OKR-A Horrible Poem】

【题解】【P3538 [POI2012]OKR-A Horrible Poem】

Analysis

1. 首先循环节和border一一对应，所以判断某个长度x是否为循环节，可以直接判断len-x是否是border，判断方法有两种，hash或者后缀数组都可以。
2. 因此有一种做法：从小到大枚举询问子串长度的所有约数，并利用上述判断方法\(O(1)\)判断，约数可以预处理出来。总复杂度\(O(q*最大约数个数)\)，但是有个点会T
3. 上述方法复杂度近似\(O(q\sqrt{n})\)，考虑优化。先提出一个引理：字符串的所有循环节都是最小循环节的倍数。（证明见Tip）。那么len一定是最小循环节的倍数，然后枚举len的所有质因子，若len/p可以作为循环节，那么len/p一定是最小循环节的倍数，令len/=p。将len的质因子枚举完后，最后的len显然就是答案。一个数质因子的个数是log级别的，可以通过本题。可以通过筛法预先筛出每个数的质因子集合。
   Tip:我们可以将字符串的循环节类比成周期函数，设存在两个循环节x,y,则f(i)=f(i+x)=f(i+y)，那么f(i)=f(i+y-x),进一步f(i)=f(i+y%x)。可以发现这个过程与辗转相除法类似。最终可以推出gcd(x,y)是循环节，因此，若存在一个循环节不是最小循环节的倍数，那么一定存在一个比最小循环节还要小的循环节，就会出现矛盾。

Code

#include
using namespace std;
//#define int long long
inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=~(x-1);
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=5e5+100;
char s[N];
int rk[N],y[N<<1],t[N],n,m=128,q,sa[N],h[N],st[N][20],mxlg[N];
vectord[N];
void getsa()
{
	for(int i=1;i<=n;++i) t[rk[i]=s[i]]++;
	for(int i=1;i<=m;++i) t[i]+=t[i-1];
	for(int i=1;i<=n;++i) sa[t[rk[i]]--]=i;
	for(int k=1;;k<<=1)
	{
		int cnt=0;
		for(int i=n-k+1;i<=n;++i) y[++cnt]=i;
		for(int i=1;i<=n;++i) if(sa[i]>k) y[++cnt]=sa[i]-k;
		for(int i=1;i<=m;++i) t[i]=0;
		for(int i=1;i<=n;++i) t[rk[i]]++;
		for(int i=1;i<=m;++i) t[i]+=t[i-1];
		for(int i=n;i;--i) sa[t[rk[y[i]]]--]=y[i],y[i]=rk[i];
		for(int i=1;i<=n;++i) rk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?rk[sa[i-1]]:rk[sa[i-1]]+1;
		m=rk[sa[n]];if(m==n) break;
	}
	for(int i=1,j,k=0;i<=n;h[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
}
void stpre()
{
	for(int i=2;i<=n;++i) mxlg[i]=(1<rk[y]) swap(x,y);
	int k=mxlg[rk[y]-rk[x]];
	return min(st[rk[x]+1][k],st[rk[y]-(1<=w) x/=d[len][j];
		}
		write(x);puts("");
	}
	return 0;
}
/*
8
aaabcabc
3
1 3
3 8
4 8
*/