【题目描述】

【输入】

【输出】

【输入样例】

abcd
aaaa
ababab
.

【输出样例】

1
4
3

题目分析

本题是一道极其经典的字符串基础题。题目给定一个长度最大为10^6的字符串，要求找出它可以由多少个相同的子串重复拼接而成，求最大的重复次数。 将题意稍作转换：要求“最大的重复拼接次数”，等价于求字符串的“最短循环节”。找到了最短循环节，用总长度除以循环节的长度，即为最终答案。 针对这种循环节判断问题，竞赛中最常用的两套利器是字符串哈希与KMP算法的next数组。

---

思考过程与解题思路

面对10^6的数据级别，朴素的O(N^2)暴力截取比对必然会超时。我们必须将单次验证的时间复杂度降到极致。

思路一：字符串哈希（降维暴力） 既然不知道最短循环节是多长，最直观的思路就是“从小到大枚举”子串的长度 i。 只要原串长度len能被i整除，我们就把原串按长度i切成若干块，逐块比对。为了把字符串比较的O(K)时间降到O(1)，我们引入前缀哈希。通过预处理前缀哈希数组，利用公式 Hash(L,R)=ans[R]−ans[L−1]×P[R−L+1]，实现O(1)的切片校验。一旦某长度i校验通过，配合贪心思想，它必然是最短循环节。

思路二：KMP算法（核心定理推导） 如果说哈希是暴力的极致优化，KMP的next数组则是数学规律上的降维打击。 在0-base下标体系中，nxt[len-1]记录的是整个字符串的最长相等真前后缀长度。 这里存在一个极其优美的物理错位规律：将字符串的“前缀”与“后缀”对齐，它们之间在物理空间上错开的距离，正是字符串自我复制的最小周期。 因此得出核心定理：最小循环节长度=字符串总长度N-最长相等真前后缀nxt[N-1]。 最后仅需验证：若总长度能被该循环节整除，则完美循环；否则，该字符串只能由它本身构成（答案为1）。

---

算法设计与时空复杂度分析

1. 字符串哈希法

• 算法设计： 利用unsigned long long自然溢出特性（隐式取模264）。采用1-base存储前缀哈希，极大地简化了区间查询时的越界判断。外层枚举循环节长度i，内层以步长i进行分块校验，遇到不匹配立即break剪枝。

• 时间复杂度： 预处理O(N)。校验阶段外层枚举因子，内层分块遍历。在加入了ans2!=sum 的极速break剪枝后，几乎不会出现极端的满载扫描，综合时间复杂度趋近于O(NlogN)，实战运行极快。

• 空间复杂度：O(N)，需维护p数组和ans哈希数组。

2. KMP算法

• 算法设计： 0-base 标准模板求解 next 数组。求出nxt[len-1]后，直接通过公式推导循环节，执行一次取模运算完成终极判断，逻辑呈线性。

• 时间复杂度： O(N)，求解一次next数组的开销。

• 空间复杂度： O(N)，需维护nxt数组。

---

易错点总结

1. 多组数据切忌滥用memset： 本题是多组测试数据，且最大长度达10^6。在KMP代码中，如果每读入一个字符串就memset(nxt,0,sizeof(nxt))，会引发海量的无用内存擦除，容易导致超时。因为pre()函数内部的for循环是严格基于索引逐个赋值的，会自动覆盖旧数据，因此无需清空。

2. 哈希匹配的内层break： 哈希校验时，一旦发现当前分块sum和基准块ans2不等，必须立刻将flag2置0并break出内层循环。若缺少此break，在遇到类似aaaaa...b这种只有末尾不同的极端构造数据时，程序将进行巨量的无效校验运算。

3. 哈希数组预处理的越界防范： 字符串最大长度为1000000。预处理次幂数组p[i]时，边界应稍大于此值（如1000005），以防最后边界访问越界导致RE。

4. KMP的下标极值： 在0-base体系中，长度为len的字符串的最后一个字符下标永远是len-1。获取全串最长前后缀必须是nxt[len-1]，切勿写成nxt[len]。

---

完整代码

方法一：字符串哈希（1-base）

//哈希做法
#include <iostream>
using namespace std;
typedef unsigned long long ull;
string s;
ull p[1000010];//存储131的i次方
ull ans[1000010];//存储字符串的前缀哈希（1-base)

//返回闭区间[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);
    //预处理131的i次方
    p[0]=1;
    for(int i=1;i<=1000005;i++) p[i]=p[i-1]*131;
    while(cin>>s){
        if(s[0]=='.') return 0;
        bool flag=0;//标记字符串s是否可以由比它短的子字符串重复连接而成
        int len=s.size();
        //1-base存储s的前缀哈希
        for(int i=1;i<=len;i++) ans[i]=ans[i-1]*131+s[i-1];
        //遍历可能的子字符串长度
        for(int i=1;i<=len/2;i++){
            //子串长度必须能被s整除
            if(len%i!=0) continue;
            bool flag2=1;//标记字符串s是否可以由长度为i的子字符串重复连接而成
            //然后计算这一段长度的子串的哈希值
            ull ans2=ans[i];
            //然后去检查子串是否和s每个相同长度的部分哈希值都相等
            for(int j=1;j<=len;j=j+i){
                //求出s每一段和子串长度相同的哈希值
                ull sum=gethash(j,j+i-1);
                //如果不同 就标记flag2为0 并退出本轮查找
                if(ans2!=sum){
                    flag2=0;
                    break;
                }
            }
            //如果检查完成后 发现可以由i重复拼接而成
            //就让标记flag为1 然后i为子串长度 输出len/i(多少个子串)
            //然后就可以退出循环了
            if(flag2==1){
                flag=1;
                cout<<len/i<<"\n";
                break;
            }
        }
        //如果不能由长度比s小的子串构成 就输出1（只能由自己组成）
        if(flag==0) cout<<1<<"\n";
    }
    return 0;
}

方法二：KMP算法（0-base）

//kmp做法 最短循环节长度=字符串长度-最长公共前后缀
#include <iostream>
using namespace std;
string s;
int nxt[1000010];//存储s[0]-s[i]的最长真公共前后缀长度

//预处理字符串s的最长公共前后缀长度 
void pre(){
    int j=0;
    int len=s.size();//字符串s长度
    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);
    while(cin>>s){
        //.即一个半角句号 此时输入结束
        if(s[0]=='.') return 0;
        int len=s.size();//字符串s长度
        //处理字符串s的next数组
        pre();
        //最短循环节长度=字符串总长度-整个字符串的最长相等真前后缀长度
        int len2=len-nxt[len-1];
        //验证该循环节是否能完整铺满整个字符串
        if(len%len2!=0) cout<<1<<"\n";//有残缺，无法构成循环
        else cout<<len/len2<<"\n";//完整铺满，输出重复拼接的次数
    }
    return 0;
}