本文共 655 字，大约阅读时间需要 2 分钟。

思路

首先不要把周期想的太复杂，其实当一个字符串a复制一次能包含字符串b（long a<long b），那a就是b的一个周期。注意周期不一定只有一个。

现在来考虑怎么写。

代码

#include
   
    #include
    
     using namespace std;long long n,ans,nxt[1000010];char s[1000010];int find(int fa){   	if(nxt[fa])	  return nxt[fa]=find(nxt[fa]);	return fa;}int main(){   	scanf("%d%s",&n,s+1);	int k=0;	for(int i=2; i<=n; i++)	 {   	 	while(k>0&&s[k+1]!=s[i])	 	  k=nxt[k];	 	if(s[k+1]==s[i])	 	  k++;	 	nxt[i]=k;	 }	for(int i=1; i<=n; i++)	   ans+=i-find(i);	cout<