题目描述

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

输入

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

输出

请输出最短的长度

样例输入

8
cabcabca

样例输出

3

题解

#include<iostream>
#include<cstring>
using namespace std;
int n,q[1000005];
char a[1000005];
int main()
{
	cin>>n;
	scanf("%s",a+1);
	int j=0;
	q[1]=0;
	for(int i=2;i<=n;i++)
	{
		while(j&&a[i]!=a[j+1])
			j=q[j];
		if(a[i]==a[j+1])
			j++;
		q[i]=j;
	}
	cout<<n-q[n]<<endl;
	return 0;
}