[BOI2009]Radio Transmission 无线传输

题目描述

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

输入输出格式

输入格式：

第一行给出字符串的长度,1 < L ≤ 1,000,000.

第二行给出一个字符串，全由小写字母组成.

输出格式：

输出最短的长度

输入输出样例

输入样例#1： 

8
cabcabca

输出样例#1： 

3

说明

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

 

分析：

本题是KMP的基础题（比模板还简单？？？），这道题求的是字符串s最小长度的循环，我们称之为“s的循环子串”，结论也就是：ans=n-next[n]。

 

CODE：

 

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn=1000005;
 5 int n,next[maxn];
 6 char s[maxn];
 7 int main(){
 8     scanf("%d%s",&n,s+1);
 9     int j=0;
10     for(int i=2;i<=n;++i){
11         if(j&&s[i]!=s[j+1]) j=next[j];
12         if(s[i]==s[j+1]) ++j;
13         next[i]=j;
14     }
15     printf("%d",n-next[n]);
16     return 0;
17 }