题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
8
cabcabca

样例输出 #1

1
3

提示

样例输入输出 1 解释

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

规模与约定

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

分析

我首先想到的是二分答案，但仔细想想不太可行。

样例中cab首尾相接，各不相同，next全0，而后一直增加，这大概可以从next数组考虑。于是打表找规律。

1
2
abcdabcdab
0000123456

猜想大概是要找后面的123456...，而答案就是前面0的个数，因为abcd各不相同，而循环节之后next数组就应该一直增加。

但这只是循环节各不相同的简单情形，如果有相同的呢？

1
2
xbbxbbx
0001234

嗯，好像也一样。那这样呢：

1
2
abaabaab
00112345

事情正起变化，因为循环节本身的结构，123456...前面不全是0了，但可喜可贺这似乎不是很影响，我们只要修正已有的结论：答案是123456...前面元素的个数。这里有一个trick，其实答案就是123456...中1的位置（下标从0开始算）。

但是，有一个很讨厌的情况！

1
2
abaabaak
00112340

这个时候答案是多少呢？根据题意我们只能把整个abaabaak作为循环节了，因此答案是8。这似乎只要加个特判？并非如此，因为next数组递减不一定是减到0，所以还有其他情况，结论需要大修特修。

1
2
3
position   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
    next   0  0  0  0  1  2  3  1  2  3  4   5   6   7   4   0
 content   a  g  c  t  a  g  c  a  g  c  t   a   g   c   t   g

上面这个例子就包含很多了。结论是令ans为next数组中第一个1的位置，在后续的扫描中若next数组递减，则更新ans=pos-next[pos]+1。

回顾之前的例子：

1
2
abaabaab
00112345

为追求形式的统一，将结论进一步修正为：令ans为next数组中第一个1的位置，在后续的扫描中若next数组不增，则更新ans=pos-next[pos]+1。

这个结论的原理其实就在next数组的定义中，这里不展开。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>

const int MAXL = 1e6+10;
char s1[MAXL];
int mynext[MAXL], L;

void getNext(){ //前置知识点，next数组
    int j = 0;
    mynext[0] = 0;
    for(int i=1; i<L; i++){
        while(j>0 && s1[i]!=s1[j]) j=mynext[j-1];
        if(s1[i]==s1[j]) j++;
        mynext[i] = j;
    }
}

int main(){
    scanf("%d%s",&L,s1); //C风格字符串
    if(L==1){printf("1");return 0;} //特判
    getNext();
    int pos = 0, ans = 1;
    
    while(!mynext[pos]){
        pos++;
        if(pos == L){
            printf("%d",L); return 0;
        }//指向尾后，next全0
    }
    ans = pos; //此时pos指向next数组中第一个1
    for(; pos<L; pos++){
        if(mynext[pos] <= mynext[pos-1]){
            //next数组第一个一定是0，所以不会越界
            ans = pos-mynext[pos]+1;
        }
    }

    printf("%d",ans);
    return 0;
}