题目描述

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

输入格式

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

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

输出格式

输出最短的长度

输入输出样例

输入 #1复制

8cabcabca

输出 #1复制

3

说明/提示

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

 

 

这道题求的是字符串ss最小长度的循环，我们称之为“ss的循环子串”

 

引入结论：

 

ans=n-next[n]

 

求出字符串的最大公共前后缀；

 

程序很短，但浓缩的都是精华（毕竟是KMP）

 

#include
      
       #include
       
        #include
        
         using namespace std;#define Q 1000005char a[Q];int p[Q];int s,i,j;int main(){    scanf("%d",&s);    scanf("%s",a+1);    for(i=2;i<=s;i++){        while(j&&a[j+1]!=a[i]){            j=p[j];        }        if(a[j+1]==a[i]){            j++;        }        p[i]=j;     }    printf("%d",s-p[s]);}