洛谷P4391：

思路

对于给定的字符串

运用KMP思想

设P[x]为前x个字符前缀和后缀相同的最长长度

则对于题目中的长度len有：

len-p[len]为第一个重复子串的最后一个字符位置

因此len-p[len]即重复子串长度

证明：

因为p[len]为前len个字符中前缀和后缀相同的最长长度

先对于一个重复串来观察

abcd abcd abcd

则对于p[12]=8 就是它后面多出来的重复串

用总长把多出来的重复串减去即可得到原始重复串的长度

通过题目已经知道原串是一条自重复串

那么不妨设x为原始重复串的长度 则x+1到len都是他重复的部分

因此我们求出p[len]就是后面重复部分的长度

则len-p[len]就满足原始重复串的长度

模拟样例：

字符串：c a b c a b c a

对应P： 0 0 0 1 2 3 4 5

则len-p[len]的位置为3

因为1~5的cabca与4~8的cabca相同

对于4~8的字符串都是原始字符串的重复部分

所以只要再补上一个b

即可满足重复串cabcabcab

代码

#include
    
     #include
     
      #include
      
       using namespace std;#define maxn 1000010char a[maxn];int p[maxn];int len,j;int main(){    scanf("%d",&len);    scanf("%s",a+1);    for(int i=2;i<=len;i++)//常规KMP求P数组     {        while(j&&a[j+1]!=a[i]) j=p[j];        if(a[j+1]==a[i]) j++;        p[i]=j;     }       printf("%d",len-p[len]);//输出原始重复串长度 }