最短周期
TAT不知道题目怎么贴不上来
zld：傻逼题
枚举答案哈希TAT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long #define p 9875321 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,pos; ll tmp[1000005],H[1000005]; char ch[1000005]; int gethash(int L,int R) { return (H[R]-H[L-1]*tmp[R-L+1]%p+p)%p; } int rejudge(int x,int L,int R) { pos=0; for(int i=0;i<R-L+1&&x+i+(pos!=0)<=n;) if(ch[x+i+(pos!=0)]!=ch[L+i]) { if(pos)return 0; else pos=x+i; } else i++; return 1; } bool jud(int len,int L,int R) { int tmp=gethash(L,R); bool flag=0; for(int i=1;i<=n;i+=len) if(i+len-1<=n) { if(gethash(i,i+len-1)!=tmp) { if(flag)return 0; if(!rejudge(i,L,R))return 0; else i++,flag=1; } } else { if(gethash(i,n)!=gethash(L,L+n-i)) { if(flag)return 0; if(!rejudge(i,L,L+n-i-1))return 0; } } return 1; } int main() { freopen("naj.in","r",stdin); freopen("naj.out","w",stdout); tmp[0]=1; for(int i=1;i<=100000;i++) tmp[i]=(tmp[i-1]*10007)%p; T=read(); while(T--) { n=read(); scanf("%s",ch+1); for(int i=1;i<=n;i++)H[i]=(H[i-1]*10007+ch[i]-'a'+1)%p; for(int i=1;i<=n;i++) if(jud(i,1,i)) { printf("%d\n",i);break; } else if(rejudge(1,i+2,min(n,i+i+1))) { if(!pos)continue; if(i+i+1>n) { printf("%d\n",i);break; } else if(jud(i,i+2,i+i+1)) { printf("%d\n",i);break; } } } return 0; } |
计数器 9320981
OI 课件=>
OI 课件=>
OrzHzwer