分析：
又是一道需要深入理解$next[]$数组的题。
因为$next[i]$表示的是第$i-1$个前缀的最长公共前后缀，那么不难想到，在$j<=i$且$next[j]$不为$0$的情况下可以得到一个最短后缀，用原串长度减去即可得到答案。
Code：
//It is made by HolseLee on 11th Aug 2018 //Luogu.org P3435 #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<iomanip> #include<algorithm> using namespace std; const int N=2e6+7; int n,nxt[N],k,cnt; long long ans; char s[N]; int main() { scanf("%d%s",&n,s); nxt[0]=nxt[1]=0;k=0; for(int i=1;i<n;++i){ while(k&&s[i]!=s[k]) k=nxt[k]; nxt[i+1]=(s[i]==s[k]?++k:0); } int ka; for(int i=1;i<=n;++i){ ka=i; while(nxt[ka])ka=nxt[ka]; if(nxt[i])nxt[i]=ka; ans+=(i-ka); } printf("%lld ",ans); return 0; }
洛谷P3435 [POI2006]OKR-Period of Words [KMP]
原文：https://www.cnblogs.com/cytus/p/9466434.html