4. 最小循环节
题目ID：8624必做题100分
最新提交：
Runtime Error
0 分
历史最高：
Wrong Answer
60 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述：
一个字符串 s 的循环节为 t，当且仅当 s 是由若干个 t 连接而成。例如 ab 就是 abababab 的循环节，同时 abab 也是 abababab 的循环节，但它们都不是 ababa 的循环节。
现给定 s，求 s 的长度最小的循环节。
输入格式：
第一行输入一个正整数 n。
第二行输入一个长度为 n 的字符串 s。
保证 s 仅有小写字母构成。
输出格式：
一行一个正整数，表示循环节长度的最小值。
样例输入：
10 ababcababc
样例输出：
5
数据规模：
1≤n≤106。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string s;
string a[1000005]={""};
int cnt,pt;
int kmp(string s2,int m){
cnt=0;
pt=0;
int ans[1000005]={0};
ans[1]=0;
for(int i=2;i<=m;i++){
while(pt>0&&s2[i]!=s2[pt+1]){
pt=ans[pt];
}
if(s2[i]==s2[pt+1]){
pt++;
}
ans[i]=pt;
}
pt=0;
for(int i=1;i<=n;i++){
while(pt>0&&s[i]!=s2[pt+1]){
pt=ans[pt];
}
if(s[i]==s2[pt+1]){
pt++;
}
if(pt==m){
//cout<<i-m+1<<endl;
cnt++;
pt=ans[pt];
}
}
return cnt;
}
int main(){
scanf("%d",&n);
cin>>s;
s=" "+s;
for(int i=2;i<=n;i++){
a[i]=a[i-1]+s[i];
}
for(int ans=1;ans<=n/2;ans++){
if(n%ans){
continue;
}
int zq=n%ans;
if(zq==kmp(a[ans],ans)){
cout<<ans;
return 0;
}
}
cout<<n;
return 0;
}
/*
*/
