#C240128D. 最短循环节(string)

标签（Label）

哈希
二分答案

网址（Website）

#C240128D. 最短循环节(string) - 洛谷

题解（Solution）

$\qquad$见题解。

代码（Code）

#include<bits/stdc++.h>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<double,double>
#define int unsigned long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
const int bas = 131;
//const int mod = 1e9+7;

char s[N];
int n;

int hsh[N],pw[N];

inline int geths(int l,int r){return (hsh[r]-hsh[l-1]*pw[r-l+1]);}

int ask(){
	For(i,1,n) hsh[i]=(hsh[i-1]*bas+s[i]);
	For(i,1,n-1){
		int del=0;//删除的字符数
		for(int j=i+1;j<=n;j+=i){
			int len=min(i,n-j+1);
			if(geths(j,j+len-1)==geths(1,len)) continue;
			if(++del==2) break;
			int l=1,r=len,mid,ans=len;
			while(l<=r){
				mid=l+r>>1;
				if(geths(1,mid)==geths(j,j+mid-1)) l=mid+1;
				else r=mid-1,ans=mid;
			}if(j+ans-1!=n){//如果不是刚好最后一段相同 
				int ed=min(j+i,n);//防止遇到末尾匹配 
				if(geths(ans,ed-j)!=geths(j+ans,ed)){del=2;break;}
			}j++;
		}if(del<2) return i;
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	string str("string");
//	freopen((str+".in").c_str(),"r",stdin);
//	freopen((str+".out").c_str(),"w",stdout);
	double Tim=clock();int T=input();
	pw[1]=bas;For(i,2,200005) pw[i]=pw[i-1]*bas;
	while(T--){
		cin>>n>>(s+1);
		if(n==1){cout<<'0';continue;}
		int len=ask();
		reverse(s+1,s+n+1);
		len=min(ask(),len);
		cout<<len<<'\n';
	}
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}