原题来自：BalticOI 2009

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

第一行给出字符串的长度 L，第二行给出一个字符串，全由小写字母组成。

输出最短的长度。

8
cabcabca

3

样例说明:

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

数据范围:

对于全部数据，1≤L≤10^6​​ 。

在字符串算法的训练中，求解“最小循环节”是一个绕不开的核心考点。很多人做过经典的 POJ 2406 (Power Strings)，那道题要求字符串必须由完整的循环节拼接而成。

今天我们要剖析的这道 BalticOI 2009 的真题，是POJ 2406的“进阶变种”。题目同样是求最短循环节，但多了一个极其关键的条件：给定的字符串，可能只是无限自我连接串的一个子串。 换句话说，它允许最后一段循环节是不完整的（有残缺的尾巴）。

例如样例 cabcabca，它的最短循环节是cab（长度为 3），由cab+cab+ca（残缺）组成。

面对这个条件变化，我们的解题思路会发生怎样的演进？本文将完整还原从“朴素哈希分块”到“哈希错位优化”，再到“KMP”的三种渐进过程。

---

思考过程与算法设计

第一阶：哈希分块暴力校验

面对寻找周期的问题，最直观的思维就是枚举。 我们从小到大枚举可能的循环节长度i。由于题目允许最后一段残缺，我们不能像以前那样只枚举到len/2，必须枚举到len。 对于每一个长度i，我们把原串按步长i进行切片，利用字符串前缀哈希O(1)比对每一个切片是否与第一个切片相等。如果前面都相等，最后再单独提取出尾部那一段“模不尽”的残缺部分，看看它是否等于循环节对应长度的前缀。

这种解法逻辑严密、符合直观直觉，但在代码实现上略显繁琐，需要处理大量的边界和取模逻辑。

第二阶：哈希错位优化 

在第一阶的分块校验中，我们做了很多“苦力活”。其实，在字符串里，判断一个长度i是否为周期，有且仅需一次校验： 判断原串的 [1,len-i]和[i+1,len] 这两段哈希值是否相等。

物理推导： 如果前缀 [1,len-i] 等于后缀 [i+1,len]，说明对于任意下标k，都有 S[k]==S[k+i]。 这就是多米诺骨牌效应：单个字符每隔i个位置就强制相等，这必然导致整个字符串在物理上被分割成了长度为i的连续循环节（无论最后有没有拼完）。 这样一来，繁琐的内层循环和尾部特判全被一行代码取代！

第三阶：KMP核心定理

当我们发现哈希优化的本质是“寻找最长相等前后缀”时，真正的天命之子——KMP算法就呼之欲出了。 在0-base下标体系中，KMP的next数组求出的nxt[len-1]，其物理意义正是整个字符串的最长相等真前后缀长度。 套用刚才的错位理论： 滑动距离 (循环节)+重合长度 (nxt数组值)=字符串总长度 即：最短循环节长度=字符串总长度-nxt[len-1]

在 POJ 2406 中，我们还需要用len%循环节==0来验证完整性；但在本题中，题目本身就允许循环节残缺，因此len-nxt[len-1]就是正解，连取模验证都不需要，直接输出即可。

---

时空复杂度分析

• 哈希分块暴力法：预处理O(N)，内外层嵌套循环加尾部特判，遇到极端恶心数据时可能退化，综合时间复杂度约为O(NlogN)，空间复杂度O(N)。

• 哈希错位优化法：预处理O(N)，单层循环枚举，内部O(1)哈希校验。时间复杂度稳定O(N)，空间复杂度O(N)。

• KMP极简法：仅需扫描一次字符串构建next数组，时间复杂度绝对O(N)，空间复杂度 O(N)。常数极小，实战运行速度最快。

---

易错点总结 

1. 哈希暴力法的枚举上限：由于允许循环节残缺，原串长度可能不足两个完整循环节（如 abcdabc周期为4），因此枚举上限必须是len，绝不能写成len/2。

2. KMP的0-base越界：获取全串最长前后缀必须是nxt[len-1]。在0-base中，写成 nxt[len]会直接读取未知内存导致RE或WA。

3. 大数据量的I/O阻塞：本题字符串长度高达 10^6，如果不加 ios::sync_with_stdio(false); cin.tie(0);，容易在读取长字符串时超时 。

---

完整代码 (三版代码)

下面保留了三种思维阶段的完整代码，并在关键位置给出了详尽注释。强烈建议同学们顺着这个思路演进阅读。

版本一：哈希分块暴力做法 (直观解法)

//哈希暴力做法
#include <iostream>
using namespace std;
typedef unsigned long long ull;
string s;
int n;//字符串长度
ull p[1000010];//存储131的i次方
ull ans[1000010];//存储字符串s的前缀哈希

//返回闭区间[l,r]的哈希值
ull gethash(int l,int r){
    if(l>r) return 0;
    return ans[r]-ans[l-1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    cin>>s;
    //预处理131的i次方
    p[0]=1;
    for(int i=1;i<=n;i++) p[i]=p[i-1]*131;
    //预处理字符串s的前缀哈希(1-base)
    for(int i=1;i<=n;i++) ans[i]=ans[i-1]*131+s[i-1];
    //获取字符串s的长度
    int len=s.size();
    //遍历可能的子串长度
    for(int i=1;i<=len;i++){
        ull ans2=ans[i];//i长度的子串所代表的哈希值
        bool flag=1;//标记字符串s是否能由i长度的子串所构成
        //挨个遍历字符串s中 所有i长度的子串
        for(int j=1;j+i-1<=len;j=j+i){
            //字符串s中 每一段i长度的子串所代表的哈希值
            ull ans3=gethash(j,j+i-1);
            //如果不同 就代表i长度不行 退出
            if(ans2!=ans3){
                flag=0;
                break;
            }
        }
        //如果相同 还要判断最后可能剩下的后缀
        if(flag==1){
            if(len%i!=0){
                //尾部剩下的模不进的一部份的哈希值
                ull ans4=gethash(len/i*i+1,len);
                //尾部剩下的模不进的部分的长度
                int len2=len-len/i*i;
         //校验残缺部分是否等于基准子串对应长度的前缀
                if(ans4==ans[len2]){
                    cout<<i;
                    return 0;
                }
            }
            else{//如果刚好可以整除 没有残缺部分 直接输出
                cout<<i;
                return 0;
            }
        }
    }
}

版本二：哈希错位优化

//哈希优化做法
//判断一个长度i是不是循环节
//仅需判断原串的[1,len-i]和[i+1,len]这两段哈希值是否相等（KMP的next数组原理）
#include <iostream>
using namespace std;
typedef unsigned long long ull;
string s;
int n;//字符串长度
ull p[1000010];//存储131的i次方
ull ans[1000010];//存储字符串s的前缀哈希

//返回闭区间[l,r]的哈希值
ull gethash(int l,int r){
    if(l>r) return 0;
    return ans[r]-ans[l-1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    cin>>s;
    //预处理131的i次方
    p[0]=1;
    for(int i=1;i<=n;i++) p[i]=p[i-1]*131;
    //预处理字符串s的前缀哈希(1-base)
    for(int i=1;i<=n;i++) ans[i]=ans[i-1]*131+s[i-1];
    int len=s.size();//字符串s的长度
    //枚举可能的周期长度i
    for(int i=1;i<=n;i++){
        //判断原串的[1,len-i]前缀和[i+1,len]后缀是否完全相等
        //等价于判断s[k]==s[k+i] 直接利用多米诺效应证明周期性 不需要再去考虑残缺尾部
        if(gethash(1,len-i)==gethash(i+1,len)){
            cout<<i;
            return 0;
        }
    }
    return 0;
}

版本三：KMP极简做法

//kmp做法 0-base
#include <iostream>
using namespace std;
int n;
string s;
int nxt[1000010];//nxt[i]代表s[0]到s[i]的最长相等真前后缀
int len;

//预处理0-base KMP的next数组
void pre(){
    int j=0;
    //0-base 下标i从1开始 nxt[0]默认为0
    for(int i=1;i<len;i++){
        while(j>0&&s[i]!=s[j]) j=nxt[j-1];
        if(s[i]==s[j]) j++;
        nxt[i]=j;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    //字符串s的长度
    len=s.size();
    //求nxt数组
    pre();
    //KMP 最小周期=总长度-整个字符串的最长公共前后缀长度
    //由于题目允许子串残缺 因此不需要进行取模验证 公式算出的即为解
    cout<<len-nxt[len-1];
    return 0;
}