Description：

求串 $S$ 的每个前缀的最大周期长度。

$1\le n \le 10^6$

Solution：

如果是最小周期，那么答案就是 $i-nxt[i]$ ，但是本题要求最大周期，也就是说要找到一个尽量小的串满足前缀等于后缀，但是可以发现如果我们求出了 $1$ ~ $nxt[i]$ 的最小的前缀等于后缀，那么当前串的最小的前缀等于后缀的长度应与之相同，而 $nxt$ 数组第一次不为 $0$ 时求得的最小前缀等于后缀和最大前缀等于后缀长度相同，于是按照这个递推就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int l;

#define MAXL 1000010

char c[MAXL];

int nxt[MAXL];

int main()

{

	scanf("%d",&l);

	scanf("%s",c + 1);

	nxt[1] = 0;

	for(int i = 2,j = 0;i <= l;++i)

	{

		while(j && c[i] != c[j + 1])j = nxt[j];

		if(c[i] == c[j + 1])++j;

		nxt[i] = j;

	}

	for(int i = 2;i <= l;++i)

		if(nxt[nxt[i]] != 0)

			nxt[i] = nxt[nxt[i]];

	long long ans = 0;

	for(int i = 1;i <= l;++i)

		if(nxt[i])ans += i - nxt[i];

	cout << ans << endl;

	return 0;

}