字符串——OKR-Periods of Words（kmp求最短相同前后缀或者说求最长循环节）

传送门：OKR-Periods of Words

思路：题目要求的是最大的前缀Q使得A是QQ的前缀，同时Q不能等于A,

比如在bababab，要使得周期最大，应该选的循环节就是bababa，

另一个有同样功能的循环节是baba，很明显第一个循环节的长度更大，使得周期也更大。

已知最小循环节的大小是n-next[n],要求最长循环节就是要求最短的相同前后缀，

为此可以让不断的让next[n]=next[next[n]],以此求得最短的相同前后缀，求法和这道题的一模一样字符串——Seek the Name, Seek the Fame（kmp应用）_北岭山脚鼠鼠的博客-CSDN博客

注意：这里因为每一个前缀都遍历到底一次，会超时，所以要让next[i]=next[next[i]],缩短后面更长的前缀的遍历次数。

传送门：

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
char a[N];
int ne[N];
int n;
ll ans;
void   get_ne()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&a[i]!=a[j+1]) j=ne[j];
        if(a[i]==a[j+1]) j++;
        ne[i]=j;
    }
}
void get_ans()
{
    int p;
    for(int i=1;i<=n;i++)
    {
        p=i;
        while(ne[p]!=0) p=ne[p];
        if(ne[i]!=0) ne[i]=p;
        ans+=i-p;
    }
}
int main()
{
    cin>>n;
    scanf("%s",a+1);
    get_ne();
    get_ans();
    cout<
 
    return 0;
}