BZOJ1355 [Baltic2009]Radio Transmission

Description

给你一个字符串,它是由某个字符串不断自我连接形成的.但是这个字符串是不确定的,现在只想知道它的最短长度是多少.

Input

第一行给出字符串的长度,1<L≤1000000. 第二行给出一个字符串,全由小写字母组成.

Output

输出最短的长度.

Sample Input

8
cabcabca

Sample Output

3

Solution

next[n]就是长度小于n最长的border,自己画下图,应该一目了然,1~n-next[n]一定是整串的循环节,那答案就是n-next[n].

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
int next[N],n,j;
char s[N];
int main(){
    scanf("%d%s",&n,s+1);
    for (int i=2;i<=n;i++){
        while (j&&s[i]!=s[j+1]) j=next[j];
        if (s[i]==s[j+1]) j++; next[i]=j; 
    }
    printf("%d",n-next[n]);
}