Description
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input
第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.
Output
输出最短的长度
Sample Input
8

cabcabca
Sample Output
3
HINT

对于样例,我们可以利用”abc”不断自我连接得到”abcabcabc”,读入的cabcabca,是它的子串

解法：根据KMP的性质，答案就是n-fail[n]

//BZOJ 1355

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000010;
char s[maxn];
int fail[maxn];
int n;

int main()
{
    scanf("%d", &n);
    scanf("%s", s+1);
    int j=0;
    for(int i=2; i<=n; i++){
        while(j>0&&s[j+1]!=s[i]) j=fail[j];
        if(s[j+1]==s[i]) j++;
        fail[i]=j;
    }
    printf("%d\n", n-fail[n]);
    return 0;
}