Description：

给一个字符串，求一个长度最短的字符串使得把这个字符串重复多遍可重叠能拼成原串。

$1\le n \le 500000$

Solution：

这个最短的字符串一定是原串的一个前缀，也一定是后缀。设 $f[i]$ 表示前缀 $1$ ~ $i$ 都被覆盖的最短长度，显然 $f[i]$ 最大是 $i$ ，用 $KMP$ 求出 $nxt$ 数组，由于 $nxt$ 是最大的前缀 $=$ 后缀，所以又有 $f[i]=f[nxt[i]]$ 。也就是说 $[1,nxt[i]]$ 和 $[i-nxt[i]+1,i]$ 的覆盖情况相同，但这种转移能转移当且仅当存在 $f[j]=f[nxt[i]]$ 且 $j\ge i-nxt[i]$ ，如果 $f[j]=f[nxt[i]]$ ，那么他们的模板串一定相同，因为是主串一个长度相同的前缀，所以可以开一个桶记录 $f$ 值为 $k$ 使得最靠后的距离 $h[k]$ ，用 $h[k]$ 作为转移，如果 $h[k]$ 都不能转移，那么谁也不能转移，因为 $h[k]$ 已经尽量靠前， $i-nxt[i]$ 已经尽量靠后了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 500010

char c[MAXL];

int nxt[MAXL];

int f[MAXL],h[MAXL];

int main()

{

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

	int l = strlen(c + 1);

	nxt[1] = 0;

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

	{

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

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

		nxt[i] = j;

	}

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

	{

		f[i] = i;

		if(h[f[nxt[i]]] >= i - nxt[i])f[i] = f[nxt[i]];

		h[f[i]] = i;

	}

	cout << f[l] << endl;

	return 0;

}