https://loj.ac/problem/10038
题目描述
给出一个字符串\(S\),以及\(q\)次询问,每次询问这个字符串子串的最短循环节。
思路
这道题是毒瘤题,一定是毒瘤题,至少\(loj\)的数据是。我有两个思路,一个\(93\)分,一个不加快读\(97\)分,加快读满分。
首先,很显然,对于一个字符串求最小循环节,枚举为其长度因数的前缀。但这样显然会\(T\),我们考虑优化。
\(①\)我们考虑可以通过预处理,快速求出一段子串内所有字母的个数,而最小循环节中的字母个数一定是所有字母数的公因数,那么最小循环节的个数一定是这个公因数的因数,才有可能是循环节。所以我们枚举\([1,\sqrt{vgcd}]\),看是否为循环节,更新答案。最后\(93\)分。
\(②\)第一个做法跑不过去的原因是枚举时候有过多的无用状态,但又难以继续优化,我们再从最初的想法开始。我们想对于最小循环节长度,它的倍数也一定是循环节。我们先用线性筛取出到原字符串长度的所有数的最小质因数。之后每次询问把询问子串的长度进行质因数分解,求出其每一个质因数,再尝试除以每一个质因数,不断缩小\(len\),最后答案就是最小循环节。
代码(方法一,93分)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull p=131,MAXN=5e5+10;
char s[MAXN];
ull sum[MAXN],power[MAXN],ans;
ull f[MAXN][30];
ull f_hash(ull l,ull r)
{
return (ull)sum[r]-sum[l-1]*power[r-l+1];
}
ull gcd(ull x,ull y)
{
return y==0?x:gcd(y,x%y);
}
void check(ull l,ull r,ull len)
{
if(f_hash(l,r-len)==f_hash(l+len,r))
ans=min(ans,len);
}
ull read()
{
ull ret=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*w;
}
int main()
{
ull n;
n=read();
gets(s+1);
power[0]=1;
for(ull i=1;i<=n;i++)
{
sum[i]=sum[i-1]*p+(s[i]-'a'+1);
power[i]=power[i-1]*p;
}
for(ull i=1;i<=n;i++)
{
for(ull j=1;j<=26;j++)
f[i][j]=f[i-1][j];
f[i][s[i]-'a'+1]++;
}
ull q;
q=read();
while(q--)
{
ull l,r;
l=read();r=read();
ull len=r-l+1,vgcd=r-l+1;
for(ull i=1;i<=26;i++)
vgcd=gcd(vgcd,f[r][i]-f[l-1][i]);
ans=1e9;
for(ull i=1;i*i<=vgcd;i++)
if(vgcd%i==0)
{
check(l,r,len/i);
check(l,r,len/(vgcd/i));
}
printf("%llu\n",ans);
}
return 0;
}
代码(正解,满分)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull p=47,MAXN=5e5+10;
char s[MAXN];
ull sum[MAXN],power[MAXN],ans,ys[MAXN],prime[MAXN],nxt[MAXN];
bool used[MAXN];
ull f_hash(ull l,ull r)
{
return (ull)sum[r]-sum[l-1]*power[r-l+1];
}
bool check(ull l,ull r,ull len)
{
return f_hash(l,r-len)==f_hash(l+len,r);
}
ull read()
{
ull res=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return res*w;
}
void write(ull x)
{
if(x>9)write(x/10);
putchar(x%10^48);
}
void writeln(ull x)
{
write(x);
putchar('\n');
}
void pri()
{
ull k=0;
for(ull i=2;i<=MAXN;i++)
{
if(!used[i])
{
prime[++k]=i;
nxt[i]=i;
}
for(int j=1;j<=k&&i*prime[j]<=MAXN;j++)
{
ull m=i*prime[j];
used[m]=1;
nxt[m]=prime[j];
if(i%prime[j]==0)break ;
}
}
}
int main()
{
ull n=read();
scanf(" %s",s+1);
power[0]=1;
for(ull i=1;i<=n;i++)
{
sum[i]=sum[i-1]*p+(s[i]-'a'+1);
power[i]=power[i-1]*p;
}
pri();
ull q=read();
while(q--)
{
ull l=read(),r=read();
ull len=r-l+1,cnt=0;
while(len!=1)
{
ys[++cnt]=nxt[len];
len/=nxt[len];
}
len=r-l+1;
for(int i=1;i<=cnt;i++)
{
int tmp=len/ys[i];
if(check(l,r,tmp))
len=tmp;
}
writeln(len);
}
return 0;
}