难度： 绿

算法： 字符串哈希，KMP

不想用 KMP，所以直接上哈希。

首先哈希一遍字符串。讲一个小技巧：

对于一个字符串 $s_1...s_n$，其循环节为 $k$ 等价于以下两个条件的交：

$1.$ $n$ 整除 $k$

$2.$ $s_1...s_{n-k}=s_{k}...s_{n}$

有了以上性质，就可以使用哈希快速判断是否满足。

然后直接从小到大判断是否可行即可。

我觉得讲的已经够了，还不懂看代码。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll; 
ll n,m,p[1000100]={1},h[1000100],b=1e9+7;
string s;
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>s;
	s="s"+s;//占位符 
	for(ll i=1;i<=n;i++) p[i]=p[i-1]*b;//求哈希 
	for(ll i=1;i<=n;i++) h[i]=h[i-1]+p[i]*s[i];
	for(ll i=1;i<=n;i++){//求答案 
		m=(n/i)*i;
		if(h[m]-h[i]==(h[m-i])*p[i]&&(h[n]-h[m])==h[n-m]*p[m]){
			cout<<i;//输出 
			return 0;
		}
	}
}

由于题意不清，在这来发题意解释：

注： 样例解释是错的。

题目描述

给定一个字符串 $s$，求其最短前缀，使得 $s$ 为这个前缀自我连接无数次组成的字符串的前缀。