学网站开发前景,深汕特别合作区公共事业局,专业网站建设网站价格,营销型网站内容正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3538 题目大意
给一个字符串#xff0c;有q个询问#xff0c;询问一个区间最短循环节。 解题思路
首先最短循环节长度一定长度的约数#xff0c;所以我们可以枚举约数#xff0c;然后判断循环节…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3538 题目大意
给一个字符串有q个询问询问一个区间最短循环节。 解题思路
首先最短循环节长度一定长度的约数所以我们可以枚举约数然后判断循环节的话只需要(l,r−t)(l,r−t)(l,r-t)和(lt,r)(lt,r)(l+t,r)这段区间相等就好了所以我们可以用hash表来O(1)O(1)O(1)来判断循环节。 时间复杂度:O(qn−−√)O(qn)O(q\sqrt{n}) 然后在约数的地方我们用素数筛来做将n−−√n\sqrt n的复杂度降低为了log nlognlog\ n 最终时间复杂度:O(q log n)O(qlogn)O(q\ \ log\ {n}) code
#includecstdio
#define ull unsigned long long
using namespace std;
const int wer13131,N500005;
ull mul[N],hash[N];
bool use[N];
int next[N],prim[N/10],ys[N/10],n,m,l,r,k,tot;
char s[N];
void prime()//素数筛优化约数
{for(int i2;in;i){if(!use[i]){prim[k]i;next[i]i;}for(int j1;jk(long long)prim[j]*in;j){next[prim[j]*i]prim[j];use[prim[j]*i]true;if(i%prim[j]0){break;}}}
}
bool check(int l1,int r1,int l2,int r2)
{return hash[r1]-hash[l1-1]*mul[r1-l11]hash[r2]-hash[l2-1]*mul[r2-l21];
}
int main()
{scanf(%d\n%s,n,s);mul[0]1;for(int i1;in;i){mul[i]mul[i-1]*wer;hash[i]hash[i-1]*wers[i-1]-a1;}//哈希prime();scanf(%d,m);for(int i1;im;i){scanf(%d%d,l,r);int lenr-l1;tot0;while(len!1){ys[tot]next[len];//记录素数len/next[len];}lenr-l1;for(int j1;jtot;j)//枚举约数{int tlen/ys[j];if(check(l,r-t,lt,r)){lent;}//判断}printf(%d\n,len);}
}
