BZOJ 1355 [Baltic2009]Radio Transmission Hash/KMP

题意: 给定一个字符串求最小循环节。 解析: 显然我们可以hash然后枚举长度判断。 复杂度O(n/1+n/2+n/3+….+n/n)=O(nlogn) 然而KMP中next数组有一个性质。 n-next[n]恰好是最小循环节长度。 所以O(n)即可解决。 代码:

;ull;int n;ull hash[N],pow[N];char s[N];ull get_hash(int l,int r){return hash[r]-hash[l-1]*pow[r-l+1];}bool check(int len){if(len==n)return 1;ull tmphash=0;int i;for(i=1;i+len-1<=n;i+=len){if(!tmphash){tmphash=get_hash(i,i+len-1);continue;}if(get_hash(i,i+len-1)==tmphash)continue;;}if(i<=n){int tmplen=n-i+1;if(get_hash(1,tmplen)==get_hash(n-tmplen+1,n))return 1;;}return 1;}int main(){scanf(“%d”,&n);scanf(“%s”,s+1);pow[0]=1;for(int i=1;i<=n;i++)pow[i]=pow[i-1]*base,hash[i]=hash[i-1]*base+s[i];int l=1,r=n,ans;for(int i=1;i<=n;i++){if(check(i)){ans=i;break;}}printf(“%d\n”,ans);};int n;char s[N];int ne[N];void getnext(){ne[0]=-1;int i=0,j=-1;while(i<n){if(j==-1||s[i]==s[j]){i++,j++;ne[i]=j;}else j=ne[j];}}int main(){scanf(“%d”,&n);scanf(“%s”,s);getnext();printf(“%d\n”,n-ne[n]);}

，但没有一个创造奇迹的人是依靠瞬间的。