正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P3538

---

題目大意

給一個字符串，有q個詢問，詢問一個區間最短循環節。

---

解題思路

首先最短循環節長度一定長度的約數，所以我們可以枚舉約數，然后判斷循環節的話只需要(l,r?t)(l,r?t)和(l+t,r)(l+t,r)這段區間相等就好了，所以我們可以用hash表來O(1)O(1)來判斷循環節。
時間復雜度:O(qn??√)O(qn)
然后在約數的地方我們用素數篩來做，將n??√n的復雜度降低為了log?nlogn
最終時間復雜度:O(q??log?n)O(qlogn)

---

code

#include<cstdio> #define ull unsigned long long using namespace std; const int wer=13131,N=500005; 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 i=2;i<=n;i++){if(!use[i]){prim[++k]=i;next[i]=i;}for(int j=1;j<=k&&(long long)prim[j]*i<=n;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-l1+1]==hash[r2]-hash[l2-1]*mul[r2-l2+1]; } int main() {scanf("%d\n%s",&n,&s);mul[0]=1;for(int i=1;i<=n;i++){mul[i]=mul[i-1]*wer;hash[i]=hash[i-1]*wer+s[i-1]-'a'+1;}//哈希prime();scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);int len=r-l+1;tot=0;while(len!=1){ys[++tot]=next[len];//記錄素數len/=next[len];}len=r-l+1;for(int j=1;j<=tot;j++)//枚舉約數{int t=len/ys[j];if(check(l,r-t,l+t,r)){len=t;}//判斷}printf("%d\n",len);} }

總結

以上是生活随笔為你收集整理的P3538-[POI2012]OKR-A Horrible Poem【hash,字符串】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。