//[POI2006] OKR-Periods of Words:https://www.luogu.com.cn/problem/P3435 //题意就是求每个子串的最小公共前后缀,也就是让我们的next数组缩到最小就可以 //这里要记忆化一下,枚举到i的时候可以直接跳到j,减少枚举次数 #include <bits/stdc++.h> //#define int long long using namespace std; const int N=1e6+10,mod=1e9+7; string s; char s1[N]; long long n,t,a[N],f[N],res,num,ans,ne[N]; bool vis[N]; int main() { std::ios::sync_with_stdio(false); cin>>n>>s1+1; for(int i=2,j=0;i<=n;i++){ while(j&&s1[i]!=s1[j+1]) j=ne[j]; if(s1[i]==s1[j+1]) j++; ne[i]=j; } for(int i=1;i<=n;i++){ int j=i; while(ne[j]) j=ne[j]; res+=i-j; if(ne[i]) ne[i]=j; } cout<<res; return 0; }