本文的核心技术内容聚焦于利用 KMP 算法中的next数组来高效检测字符串前缀是否由循环节构成并计算其最大重复次数。该算法通过数学推导将循环节问题转化为对next数组值的简单算术判断从而在 O(n) 时间复杂度内解决大规模数据问题。一、核心算法原理与推导算法的理论基础建立在 KMP 算法next数组的定义之上。next[i]表示字符串前i个字符构成的子串的最长公共前后缀的长度。当字符串s[1...i]由k个完全相同的循环节P构成时其总长度i k * LL为循环节长度。根据next数组的语义next[i]等于前k-1个循环节的总长度即next[i] (k-1) * L。联立这两个等式i k * Lnext[i] (k-1) * L两式相减可得循环节长度L i - next[i]。进一步推导当i % (i - next[i]) 0时表明长度i恰好是循环节长度L的整数倍即该前缀由完整的循环节构成 。此时循环节出现的次数即题目要求的 K 值为K i / L i / (i - next[i])。二、算法步骤与关键判断基于上述原理算法实现分为两个主要步骤构建next数组对输入的字符串S执行标准的 KMP 预处理计算出每个位置i通常下标从 1 开始对应的next[i]值。扫描与输出从i 2开始因为题目要求i 1对每个前缀位置i进行判断条件一i % (i - next[i]) 0条件二i / (i - next[i]) 1即K 1确保循环节至少重复两次若同时满足以上两个条件则前缀s[1...i]具有循环节输出其长度i和对应的重复次数K i / (i - next[i])。三、实例解析以博客中给出的字符串aabaabaabaab(N12) 为例其next数组值如下表所示下标从1开始i123456789101112T[i]aabaabaabaabne[i]012123456789根据算法进行判断当 i6i - next[6] 6 - 3 36 % 3 0且6 / 3 2 1。因此前6个字符aabaab由长度为3的循环节aab重复2次构成。当 i12i - next[12] 12 - 9 312 % 3 0且12 / 3 4 1。因此整个字符串由循环节aab重复4次构成 。四、算法代码实现要点博客提供的 C 代码实现了上述完整逻辑关键点包括getNext函数采用经典的 KMP 算法预处理模板构建next数组。主逻辑循环在main函数中对于每个长度i从 2 到n直接应用公式if(i%(i-ne[i])0 i/(i-ne[i])1)进行判断和输出 。该算法的时间复杂度为 O(N)空间复杂度为 O(N)能够高效处理题目中 N 高达 10^6 的数据范围。参考来源AcWing 141周期 ← KMP 算法 next 数组判断“循环节”