题目传送门

题目

题目描述

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

输入格式

第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1 < L \le 10^6$。

题解

方法一：暴力求解

从字符串$s_1$的第一个字符开始，长度从小到大枚举前缀，将所有枚举出的前缀前后连接与原字符串匹配，输出长度最小的前缀的长度即可。

简单、暴力，但是没有分。

方法二：KMP算法

本题并不是KMP算法的直接应用，而是对KMP算法思想的灵活转化。

首先，你需要知道KMP算法中的$next$数组是什么。（KMP的详细讲解：《重述：KMP算法》《KMP算法》两篇文章）

定义一个字符串$s $的 border 为$s $的一个非$s$本身的子串$t$，满足$t$既是$s $的前缀，又是$s $的后缀。对于$s$，其每个长度为$ i $前缀$s′$的最长 border $t′$的长度就是$next_i$的值。这个定义的确是不容易理解的，推荐去看上面两篇文章。

现在，我假设你已经知道了KMP算法的原理了，那么问题在于这道题目与KMP的$next$数组有什么关系呢？

首先给出答案：对于长度为$n$的字符串$s$，这道题的答案就是$n-nxet_n$

首先定义最短的周期字串$T$，一个周期序列，无论从序列的第几位往后数，其周期的长度不会改变，改变的只是循环节，所以对于本题而言，可以将字符串的第一个字符设置为周期字串$T$的第一个字符。根据$next$数组的定义可以知道，$next_n$表示的是整个字符串相同的前缀和后缀最大长度，假设这个长度是$a$，则最后$a$个字符一定位于$T$的开头部分，因为最后$a$个字符与前$a$个字符完全相同，将最后的$a$个字符删掉，剩下的就是一个周期$T$，想不开的话可以画一个图模拟一下。

至此，问题解决。

代码

Fast命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
char s[M];
int nxt[M],n;
int main(){
    read(n);
    scanf("%s",s+1);
    int j=0;
    for(int i=2;i<=n;i++){
        while(j&&s[j+1]!=s[i])
            j=nxt[j];
        if(s[j+1]==s[i])
            j++;
        nxt[i]=j;
    }
    print(n-nxt[n]);
    return 0;
}