【BZOJ2795】[Poi2012]A Horrible Poem hash
2024-09-30 00:55:48
【BZOJ2795】[Poi2012]A Horrible Poem
Description
给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。
Input
第一行一个正整数n (n<=500,000),表示S的长度。
第二行n个小写英文字母,表示字符串S。
第三行一个正整数q (q<=2,000,000),表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n),表示询问字符串S[a..b]的最短循环节长度。
Output
依次输出q行正整数,第i行的正整数对应第i个询问的答案。
Sample Input
8
aaabcabc
3
1 3
3 8
4 8
aaabcabc
3
1 3
3 8
4 8
Sample Output
1
3
5
3
5
题解:回忆用KMP求一个单词最短循环节的方法,如果next[n]>=n/2,则最短循环节为n-next[n]。
那么我们就得出了O(1)判断一个长度x是否是给定串的循环节的方法,直接用hash判断s[l...r-x]和s[l+x...r]是否相等即可,那么我们思考这个最短长度是什么。
首先如果x是该串的循环节,则2x,3x也一定是该串的循环节,并且我们已知原串长度len一定是它本身的循环节,那么x一定是len的约数。我们可以将len分解质因数,x的每个质因子的次数一定<=len中每个质因子的次数,从大到小枚举这个次数即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll m1=998244353;
const ll m2=100000007;
const int maxn=500010;
int n,q,num,ans;
char str[maxn];
int pri[maxn],lp[maxn];
ll b1[maxn],b2[maxn],h1[maxn],h2[maxn];
bool np[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool check(int a,int b,int c,int d)
{
return (h1[b]-h1[a-1]*b1[b-a+1]%m1+m1)%m1==(h1[d]-h1[c-1]*b1[d-c+1]%m1+m1)%m1&&(h2[b]-h2[a-1]*b2[b-a+1]%m2+m2)%m2==(h2[d]-h2[c-1]*b2[d-c+1]%m2+m2)%m2;
}
int main()
{
scanf("%d%s%d",&n,str+1,&q);
int i,j,a,b,c;
for(i=2;i<=n;i++)
{
if(!lp[i]) pri[++num]=lp[i]=i;
for(j=1;j<=num&&i*pri[j]<=n;j++)
{
lp[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
}
}
for(b1[0]=b2[0]=1,i=1;i<=n;i++)
{
h1[i]=(h1[i-1]*233+str[i])%m1,h2[i]=(h2[i-1]*233+str[i])%m2;
b1[i]=b1[i-1]*233%m1,b2[i]=b2[i-1]*233%m2;
}
for(i=1;i<=q;i++)
{
a=rd(),b=rd(),c=ans=b-a+1;
while(c!=1)
{
if(check(a,b-ans/lp[c],a+ans/lp[c],b)) ans/=lp[c];
c/=lp[c];
}
printf("%d\n",ans);
}
return 0;
}//8 aaabcabc 3 1 3 3 8 4 8
最新文章
- 第一篇 Entity Framework Plus 之 Audit
- 101 LINQ Samples
- 【前端】使用CSS使元素居中的几种方式
- codevs 1531 山峰
- loadrunner以最后出现的字符串为分割符函数实现
- xdebug影响php运行速度
- 疯狂的ASP.NET系列-第一篇:啥是ASP.NET后续
- 利用zxing制作彩色,高容错,支持中文等UTF编码的QR二维码图片
- web 模板 类似京东左侧的导航栏
- linux学习笔记2:linux 下java开发的软件安装
- [转]PHP echo, print, printf, sprintf函数的区别和使用
- NFC协议学习分享
- ADO.NET知识的运用一(Day 26)
- 【原创】构建高性能ASP.NET站点 第五章—性能调优综述(后篇)
- Day1-python理论基础
- VB.NET生成重复窗体
- Jetson TX2安装固态硬盘(原创)
- 性能测试工具 wrk 使用教程
- 小甲鱼Python第四讲课后习题
- 手把手实战:eclipse 搭建 SpringMvc 框架环境
热门文章
- TroubleShoot: SharePoint 2013: ExecuteOrDelayUntilScriptLoaded 页面发布后不执行的问题
- 洛谷 P 1514 引水入城==Codevs 1066
- 机器人程序设计——之如何正确入门ROS | 硬创公开课(附视频/PPT)【转】
- Linux 之 MySQL主从同步
- Laravel 基础知识
- PhPStorm 快捷键使用(转载)
- mysql 新增用户并授权
- [翻译] NumSharp的数组切片功能 [:]
- lms111,rplidar 方向和起始角
- 济南day4