刷过 OJ 算法题的人对“字符串乘方”这四个字应该不陌生。尤其 POJ 2406 Power Strings 这道经典题几乎每个学 KMP 的人都被它虐过一遍。它的核心问题一句话就能讲明白给定一个字符串判断它能不能由某个更短的字符串重复若干次得到如果能最大重复次数是多少。乍一听这事特别简单不就是找循环节吗可一旦真上手你会发现里面有好多坑。比如我当年用暴力枚举因子写了个一看就对的版本结果交上去直接超时后来换了 KMP 的 Next 数组又因为循环节判定条件写反WA 到怀疑人生。这篇文章就围绕“字符串乘方”这个主题把背后的数学模型、KMP 解法原理、哈希方案、多语言实现和常见坑位一次讲清楚希望能帮你少走弯路。这篇内容适合三类人看正在刷算法题的学生、准备面试的开发者、以及工作中需要对字符串做模式分析的工程师。前面部分从数学定义讲起中间是多语言可执行的代码后面是调试技巧和真实场景应用你可以按需跳到对应部分。1. 字符串乘方到底在问什么1.1 一眼看穿题面先看一个最简单的形式给定字符串s ababab它能被ab重复 3 次得到所以答案是 3。再比如s abcabcabc答案是 3因为它是abc的 3 次乘方。但如果给你s abababa你会发现它没法由某个短串完整重复得到此时答案就是 1或者说它只能看作自身的一次乘方。这类问题的输入通常只给一个字符串有的版本会附带一个值 m问从字符串中划分出多少个长度不小于 m 的乘方子串这种属于进阶变体。更经典的形式是 POJ 2406 这样的多测输入字符串以英文句号.单独一行表示结束。不管题面怎么包装核心命题只有一个找出给定字符串的最小循环节长度然后让总长度除以它得到最大幂次。在刷题网站上这类题目的数据规模通常是 10 的 5 次方到 10 的 6 次方级别。这就意味着 O(n^2) 的做法基本没戏你需要的是线性复杂度或者接近线性的复杂度。1.2 数学建模从乘方到循环节把问题抽象成数学语言设字符串 S 的长度为 n如果能找到一个长度为 d 的字符串 T使得 S 等于 T 重复 k 次那么必然有 n d * k且对于 S 中的任意位置 i满足 S[i] S[i d]这里的下标从 0 开始且 i d n。这个等式是判断“是否存在周期 d”的原始定义。注意这里我用的是“周期”而不是“循环节”。严谨地说如果存在某个正整数 p使得对所有合法的 i 都有 S[i] S[i p]那么 p 叫做 S 的一个周期。而循环节要求 p 必须整除 n也就是整段字符串正好由若干完整的周期拼成。我们可以枚举这个 d先找出 n 的所有因子从小到大逐个验证。一旦某个 d 满足“以 d 为间隔的所有对应位置字符相等”它就是一个可行循环节此时最大幂次就是 n / d。因为我们在从小到大枚举因子所以第一个验证成功的 d 就是最小循环节长度对应的 n / d 就是最大幂次。这种暴力验证的思路时间复杂度是 O(n * τ(n))其中 τ(n) 是 n 的因子个数。n 为 1e6 时因子个数最多也就二百多个遍历一遍字符串也完全吃得消所以它其实并不是一无是处。很多新手不知道这一点一上来就追求 KMP反而把更简单的实现方式忽略了。1.3 周期与循环节的区别这里必须单独拉出来讲因为这是最容易踩坑的地方。看字符串abcab长度 n 5它的前缀abc重新出现时我们可以说 3 是它的一个周期吗验证一下S[0] aS[3] a相等S[1] bS[4] b相等。确实p 3 是一个周期。但 3 不整除 5所以abcab不能由某个短串重复得到它自己的乘方幂次就是 1。用 KMP 算出来的 Next 数组其实可以快速得到字符串的最小周期但这个“最小周期”不一定能做“最小循环节”。很多人在这里翻车就是因为只算了n - next[n-1]没判断是否能整除结果把abcab这种字符串错误地当成了周期串。判断逻辑必须是两层的第一n % (n - next[n-1]) 0第二n / (n - next[n-1])才是最大幂次 k。如果不满足整除条件答案直接是 1。2. 三种主流解法与选型底层逻辑2.1 暴力枚举因子暴力法的思路很直接对 n 的每个因子 d逐个检查 S[i] 是否等于 S[i d]。写起来大概长这样def max_power_brutal(s: str) - int: n len(s) for d in range(1, n 1): if n % d ! 0: continue ok True for i in range(n - d): if s[i] ! s[i d]: ok False break if ok: return n // d return 1这个实现里外层循环是 d从 1 试到 n只关心能整除的 d。内层循环比较所有相隔 d 的位置是否相等。如果全部相等说明 d 是循环节直接返回 n // d。它的优点是完全不需要任何算法基础甚至可以手工推算。缺点是当数据量大且字符串字符分布非常均匀时例如全 a 串aaaaaaaaaa每个内层循环都要走到最后才退出整体耗时偏高。但在面试中如果你先写出暴力版再和面试官讨论如何优化到 KMP反而是一种稳妥的沟通策略。2.2 KMP 前缀函数真正的正解KMP 的 Next 数组在字符串周期问题里是核心。这里我不打算展开 KMP 匹配的全过程只讲它和周期的关系。定义前缀函数 pi[i] 表示字符串 S 的子串 S[0..i] 的最长相等真前缀和真后缀的长度。比如s ababab它的 pi 数组为[0, 0, 1, 2, 3, 4]。整个字符串的最后一个 pi 值是 4那么最长 border 的长度就是 4而n - pi[n-1] 6 - 4 2这个 2 就是最小周期。又因为 6 能被 2 整除所以最小循环节就是长度 2 的ab幂次为 3。为什么n - pi[n-1]会等于最小周期原理其实不复杂。如果串的前缀和后缀有长度为 b 的公共部分那么把开头 b 个字符和结尾 b 个字符对齐后中间就空出了一段长度为 n - b 的区域这段区域就是周期。你可以想象成军队绕操场跑步排头跑到某个位置队尾刚好补上两个位置之间的间距就是一个周期的步长。计算前缀函数的递推也不难pi[0] 0从 i 1 开始每次取 j pi[i-1]当 S[i] ! S[j] 时把 j 回退到 pi[j-1]直到 j 为 0 或 S[i] S[j]。如果 S[i] S[j]则 j 加一pi[i] j。这个递推过程其实就是 KMP 失配时的跳转逻辑理解了这一点你就不会再把 next 数组背混了。2.3 滚动哈希另一种优雅的路线如果你把字符串看成一个大整数那比较两个子串是否相等可以用哈希 O(1) 完成。滚动哈希的做法是预处理出整个字符串的前缀哈希和一个对应的幂次数组然后枚举因子 d用哈希快速判断第 i 段和第 i d 段是否相同。以一个质数 base 对整个串做多项式哈希哈希公式为hash[i] (hash[i-1] * base code(S[i])) % mod判断 S 是否由长度为 d 的子串重复得到只需检查整个串的哈希是否等于把长度为 d 的前缀哈希按重复的方式拼接后的哈希。拼接一次的公式是repeat_hash hash[d] * (base^(n-d) base^(n-2d) ... 1) % mod这个公式里的几何级数求和可以预处理幂次数组后 O(1) 算出。实际比较时甚至可以直接对每个分段哈希逐个比较复杂度同样是 O(n * τ(n))但因为每次比较是 O(1)常数很小。不过哈希最大的问题是有碰撞风险。虽然选一个大质数比如 1e97 或 1e99再搭配 64 位无符号整数溢出取模碰撞概率已经低到可以忽略但竞赛中如果数据被特殊构造单哈希仍可能被卡。稳妥做法是双哈希用两个不同的 mod 和 base两个哈希都必须匹配才认定相等。2.4 不同方法怎么选方法时间复杂度空间复杂度适用场景暴力枚举因子O(n * τ(n))O(1)教学演示、小数据规模KMP 前缀函数O(n)O(n)绝大多数竞赛和面试题滚动哈希O(n * τ(n))O(n)需要同时判断多个子串时后缀数组O(n log n)O(n)需要做更复杂的周期分析实际做题时我优先推荐 KMP 前缀函数因为它稳定、好解释、不会碰撞。只有当你需要在一个长字符串里同时查多个子串的幂次关系时滚动哈希才会体现出明显优势因为哈希值可以 O(1) 拿到任意子串的比较结果。3. 多语言代码落地实录3.1 C 语言版POJ 2406 的完整 AC 代码先看最经典的 C 语言实现。POJ 2406 的输入以单独一行.终止每组数据是一个不含空格的字符串你需要在输出时打印最大幂次数。完整代码如下#include stdio.h #include string.h #define MAXN 1000005 char s[MAXN]; int pi[MAXN]; int main(void) { while (scanf(%s, s) ! EOF) { if (s[0] . s[1] \0) break; int n (int)strlen(s); pi[0] 0; for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) j; pi[i] j; } int cycle n - pi[n - 1]; if (n % cycle 0) { printf(%d\n, n / cycle); } else { printf(1\n); } } return 0; }这段代码里scanf(%s, s)能自动跳过空白字符包括换行和空格所以多测输入处理起来非常省心。判断结束条件时我特意加了s[1] \0确保真的只有一个点才结束防止把. 其他字符这种输入误判。cycle的计算是整个程序的核心。注意我优先判断了整除性再输出幂次。如果你把整除判断漏掉直接输出n / cycle遇到abcab这类字符串就会得到错误答案输出一个不存在的幂次。3.2 C 版用 vector 和 string 简化C 的代码基本就是把 C 版本的数组换成vectorint字符串换成std::string更方便处理动态长度。核心求解函数可以单独封装#include iostream #include vector #include string using namespace std; int max_power(const string s) { int n (int)s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) j; pi[i] j; } int cycle n - pi[n - 1]; if (n % cycle 0) return n / cycle; return 1; } int main() { string s; while (cin s) { if (s .) break; cout max_power(s) \n; } return 0; }这里我使用的pi[i - 1]表示前缀函数也就是最长 border 长度而不是 KMP 匹配时常用的失配指针。两者的区别在于失配指针有时会保存pi[i]对应的下标这个下标等于pi[i]的值而前缀函数保存的是长度。只要你在比较时用的是长度而非下标代码就不会出问题。3.3 Python 版写起来最短但要注意性能Python 实现和 C 在逻辑上完全一致只是要注意防止在大数据量下超时。用列表存储 pi 数组循环内部尽量减少属性访问能提升不少速度def max_power(s: str) - int: n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and s[i] ! s[j]: j pi[j - 1] if s[i] s[j]: j 1 pi[i] j cycle n - pi[-1] if n % cycle 0: return n // cycle return 1在 OJ 上跑 Python 版时如果遇到 n 为 1e6 级别的输入虽然 KMP 本身是线性的但 Python 的大循环还是会有常数开销。一个常见的优化是用 PyPy 提交或者把读入从input()改成sys.stdin.buffer.read().split()一次性读入所有字符串再逐条处理能显著减少 I/O 时间。3.4 Java / C# / JavaScript 的要点Java 的String.charAt()在循环里反复调用会有一些性能损耗可以先转成字符数组再处理计算前缀函数时用char[] arr s.toCharArray()之后arr[i]的访问比s.charAt(i)更快。C# 则要注意字符串是不可变类型频繁做Substring是反面教材这里只用索引访问字符不需要拼接所以问题不大。JavaScript 版跑在 Node.js 上时要注意s[i]在字符串上是可用的但s.length很大时递归不可取用普通for循环即可。函数式写法或者正则匹配在这种问题上虽然简短但性能远不如显式循环。3.5 输入解析与多测用例处理字符串乘方题目中输入格式常见两种第一种是像 POJ 2406 那样每行一个字符串单独一行.表示结束第二种是像 HDU 1358 那样给一个 n 和一个字符串让找出所有前缀中能由某个循环节重复得到的位置。第二种情况需要你在构造 pi 数组的同时检查每个位置的前缀。核心判断是(i 1) % cycle 0其中i 1是当前前缀长度。一旦满足条件说明前缀 S[0..i] 是一个完整的乘方串循环节长度是 cycle幂次是(i 1) / cycle。把这一判断放在求 pi 的循环里同步做就不会额外增加时间复杂度。4. 沉迷踩坑常见问题与排查思路4.1 next 数组定义搞混这是新手最容易懵的地方。同样是“next 数组”有的教程用next[0] -1表示失配指针的起点有的直接用前缀函数。如果把这两种实现混着用最典型的问题就是计算cycle时多 1 或者少 1。我自己的习惯是统一用前缀函数的定义pi[0] 0计算出的pi[i]永远是长度。这样cycle n - pi[n-1]的语义非常清楚它是整个字符串的最小周期长度。如果你用的是next[0] -1的版本那么对应关系会变成cycle n - (next[n] 1)这个next[n]往往存储在数组末尾的下一个位置。别去硬背哪种写法更合理挑一种顺手的然后每次都用它代码就不容易错。4.2 边界条件空串、单字符、全相同字符边界条件绝对是判题机最爱的陷阱。先看空串有些题目的输入可能包含空行如果你直接读入后调用求 pi 的逻辑n - pi[-1]会访问不存在的元素。所以进入主逻辑前必须判断n 0此时没有幂次可谈题目通常也不会给出这种数据但健壮性处理不能少。再看单字符a它的 n 1pi[0] 0cycle 11 % 1 0输出 1 或者 1 都没问题。但有的同学会在n 1时产生疑惑它算不算最小周期串严格来说任何字符串都可以看作自身的一次乘方所以答案是 1。全相同字符aaaa是最好的测试数据pi 数组是[0, 1, 2, 3]cycle 1整除成立答案是 4。如果这个数据你的代码输出不了 4说明 pi 递推里的小等号可能写漏了。4.3 大小写、空白与隐藏字符有些题目会要求忽略大小写后判断字符串是否为乘方串比如给你AbAbAb让你大小写不敏感地返回 3。解决思路很简单先对字符串做一次统一大小写处理变成小写再跑 KMP。这里必须明确一点算法层面不能依赖运行环境的默认配置也不能指望数据库的排序规则来帮忙。你必须在自己的代码里显式调用tolower或toLowerCase。空白字符也是隐藏大坑。如果字符串是从文件或者网络中读取的可能带换行符\n或回车符\r。C 语言里scanf(%s, s)会自动处理这部分但如果你用fgets记得用strcspn把末尾换行去掉。Python 的input()会自动去掉末尾换行但不会去掉中间的空格。4.4 哈希冲突与取模选质数用哈希法时质数的选择经常被忽视。base 可以取一个奇数比如 13331、131 等mod 最好取一个大质数比如 1e97、1e99。如果你的字符串只包含小写字母base 选择 131 这类数值后碰撞概率很小但如果包含任意 ASCII 字符建议把 base 取大一些或者直接用无符号 64 位整数自然溢出取模。自然溢出取模的本质是 mod 2^64这在实际中运行极快但理论上它是合数。在竞赛中被精心构造的数据确实可能卡掉单哈希所以稳妥的工程方案是双哈希准备两组 base 和 mod只有两个哈希都匹配时才认为子串相等。代价是计算量翻倍但在当前算力下完全可接受。4.5 大字符串场景的内存与 IO当字符串长度达到 1e6 或 1e7 级别内存和 IO 就成了主要瓶颈。C 语言的全局数组char s[MAXN]能轻松容纳 1e6 个字符但如果长度来到 1e7就要考虑malloc动态分配。pi 数组的int类型在 4 字节下1e7 大约占 40MB内存紧张时可以把int换成short但要注意 n 不能太大。IO 方面C 语言可以用scanfC 建议关闭同步ios::sync_with_stdio(false)Python 一定要用sys.stdin.buffer.read()。这些 IO 优化在你只需要跑一次算法时效果不明显但在多测用例中能差出几倍时间。5. 字符串乘方在真实场景里的影子5.1 文本压缩与字典构造字符串乘方问题和文本压缩之间有直接关系。如果一段文本由多段完全相同的子串拼接而成那我们可以只存储一份子串和重复次数这就是最简单的字典压缩思想。实际工程中的 LZW 压缩、zip 压缩算法里会大量用到字符串匹配和周期检测只不过实现细节更复杂。在数据备份和日志去重领域这种思路更实用。比如若干台设备上报的日志每条日志开头都包含相同的设备标识和时间戳通过检测这段公共前缀的“循环节”可以显著减少存储量。我之前在做一个日志采集平台时就遇到过磁盘写满的问题后来对日志按前缀做了乘方聚合存储量直接降了一个数量级。5.2 生物信息学中的串联重复检测DNA 和蛋白质序列里经常出现串联重复结构比如ATATAT这样由短片段 repeated 的序列。这种重复与许多遗传疾病相关所以检测一个长序列中是否存在某个片段的多次串联是基因数据分析的常见需求。生物信息学里的序列长度动辄上亿个碱基KMP 前缀函数这种 O(n) 算法在这里就很有优势。更进阶的题目还会结合滑动窗口对每个长度为 m 的子序列判断它是否为乘方串这就完全是把字符串乘方问题放到大数据场景里重新包装了。5.3 代码审计重复代码块挖掘在工程代码里如果一段代码被原样复制粘贴了很多次我们可以把它看作某个“代码块”的乘方结构。对代码文本做预处理去掉空格和注释后再检测乘方关系能快速找到重复度最高的模块。这类工具在很多大厂内部的代码质量平台里都有实现底层核心就是字符串周期检测。从复杂度上分析一个包含 n 个字符的代码文件跑一遍 KMP 前缀函数 O(n) 就能找到所有能被短块重复覆盖的连续区间。相比之下用暴力比较两两代码块的做法是 O(n^2)在大型代码仓库上根本跑不动。5.4 变体题带权字符、多次询问、逆序性质刷题时你会碰到很多字符串乘方的变体。比如题目给一个长度为 n 的字符串其中只包含r、g、b三种字符再给一个值 m让你统计有多少个长度不小于 m 的子串是乘方串。这类题目通常要结合滑窗和哈希先枚举循环节长度 d用滚动哈希快速比较每段是否相等再统计满足长度条件的数量。还有一种常见变体是结合回文。因为如果 S T^k那么 S 的逆序reverse(S)等于reverse(T)^k乘方关系在反转操作下保持成立。利用这个性质可以快速判断一个字符串和它的逆序是否存在相同的循环节进而解决一些复杂的双串匹配问题。6. 踩完这些坑之后我的实操建议6.1 不要死记模板理解 border 才是关键以前我备考时也背过 KMP 模板但一到变体题还是会卡住。后来我把 Next 数组彻底理解成“最长 border 长度”之后很多题就突然通了。字符串的 border 就是前缀和后缀相同的部分周期问题的本质就是利用 border 来说事。你只要记住最小周期等于 n 减去整个字符串的 border 长度然后判断是否能整除。这一条规则能覆盖八成字符串周期题。6.2 遇到类似题目先写暴力再优化竞赛里有句经验先写个正确的暴力程序再拿它和数据生成器对拍用来验证高效算法的正确性。字符串乘方问题也适合这么做。先写 O(n * τ(n)) 的因子枚举版本再写 KMP 版本然后构造随机小串和大串对比输出。这个方法能帮你快速发现整除判断、下标偏移这类隐蔽 bug。6.3 最小循环节提取的一个调试技巧如果你需要用循环节去还原最小重复子串可以拿到cycle长度后直接取原串前cycle个字符作为 T。但这只能在你已经确认整除条件成立时才有效否则前 cycle 个字符并不是真正的循环节。我在调试时经常用一个工具函数专门打印出 pi 数组和推导出的周期值这样能直观看到算法走到了哪一步也方便对比不同字符串下 border 长度的变化。字符串乘方看似是个小题但背后牵连着字符串哈希、前缀函数、周期定理这些核心知识点。把它彻底吃透你在处理字符串匹配、压缩算法、甚至代码分析任务时都会比别人多一层底层理解。我自己在这道题上踩过的坑就是最好的教学案例先搞清楚数学定义再选择合适的算法实现最后用边界数据验证这条路径几乎适用于所有算法题。
刷过 OJ 算法题的人对“字符串乘方”这四个字应该不陌生。尤其 POJ 2406 Power Strings 这道经典题几乎每个学 KMP 的人都被它虐过一遍。它的核心问题一句话就能讲明白给定一个字符串判断它能不能由某个更短的字符串重复若干次得到如果能最大重复次数是多少。乍一听这事特别简单不就是找循环节吗可一旦真上手你会发现里面有好多坑。比如我当年用暴力枚举因子写了个一看就对的版本结果交上去直接超时后来换了 KMP 的 Next 数组又因为循环节判定条件写反WA 到怀疑人生。这篇文章就围绕“字符串乘方”这个主题把背后的数学模型、KMP 解法原理、哈希方案、多语言实现和常见坑位一次讲清楚希望能帮你少走弯路。这篇内容适合三类人看正在刷算法题的学生、准备面试的开发者、以及工作中需要对字符串做模式分析的工程师。前面部分从数学定义讲起中间是多语言可执行的代码后面是调试技巧和真实场景应用你可以按需跳到对应部分。1. 字符串乘方到底在问什么1.1 一眼看穿题面先看一个最简单的形式给定字符串s ababab它能被ab重复 3 次得到所以答案是 3。再比如s abcabcabc答案是 3因为它是abc的 3 次乘方。但如果给你s abababa你会发现它没法由某个短串完整重复得到此时答案就是 1或者说它只能看作自身的一次乘方。这类问题的输入通常只给一个字符串有的版本会附带一个值 m问从字符串中划分出多少个长度不小于 m 的乘方子串这种属于进阶变体。更经典的形式是 POJ 2406 这样的多测输入字符串以英文句号.单独一行表示结束。不管题面怎么包装核心命题只有一个找出给定字符串的最小循环节长度然后让总长度除以它得到最大幂次。在刷题网站上这类题目的数据规模通常是 10 的 5 次方到 10 的 6 次方级别。这就意味着 O(n^2) 的做法基本没戏你需要的是线性复杂度或者接近线性的复杂度。1.2 数学建模从乘方到循环节把问题抽象成数学语言设字符串 S 的长度为 n如果能找到一个长度为 d 的字符串 T使得 S 等于 T 重复 k 次那么必然有 n d * k且对于 S 中的任意位置 i满足 S[i] S[i d]这里的下标从 0 开始且 i d n。这个等式是判断“是否存在周期 d”的原始定义。注意这里我用的是“周期”而不是“循环节”。严谨地说如果存在某个正整数 p使得对所有合法的 i 都有 S[i] S[i p]那么 p 叫做 S 的一个周期。而循环节要求 p 必须整除 n也就是整段字符串正好由若干完整的周期拼成。我们可以枚举这个 d先找出 n 的所有因子从小到大逐个验证。一旦某个 d 满足“以 d 为间隔的所有对应位置字符相等”它就是一个可行循环节此时最大幂次就是 n / d。因为我们在从小到大枚举因子所以第一个验证成功的 d 就是最小循环节长度对应的 n / d 就是最大幂次。这种暴力验证的思路时间复杂度是 O(n * τ(n))其中 τ(n) 是 n 的因子个数。n 为 1e6 时因子个数最多也就二百多个遍历一遍字符串也完全吃得消所以它其实并不是一无是处。很多新手不知道这一点一上来就追求 KMP反而把更简单的实现方式忽略了。1.3 周期与循环节的区别这里必须单独拉出来讲因为这是最容易踩坑的地方。看字符串abcab长度 n 5它的前缀abc重新出现时我们可以说 3 是它的一个周期吗验证一下S[0] aS[3] a相等S[1] bS[4] b相等。确实p 3 是一个周期。但 3 不整除 5所以abcab不能由某个短串重复得到它自己的乘方幂次就是 1。用 KMP 算出来的 Next 数组其实可以快速得到字符串的最小周期但这个“最小周期”不一定能做“最小循环节”。很多人在这里翻车就是因为只算了n - next[n-1]没判断是否能整除结果把abcab这种字符串错误地当成了周期串。判断逻辑必须是两层的第一n % (n - next[n-1]) 0第二n / (n - next[n-1])才是最大幂次 k。如果不满足整除条件答案直接是 1。2. 三种主流解法与选型底层逻辑2.1 暴力枚举因子暴力法的思路很直接对 n 的每个因子 d逐个检查 S[i] 是否等于 S[i d]。写起来大概长这样def max_power_brutal(s: str) - int: n len(s) for d in range(1, n 1): if n % d ! 0: continue ok True for i in range(n - d): if s[i] ! s[i d]: ok False break if ok: return n // d return 1这个实现里外层循环是 d从 1 试到 n只关心能整除的 d。内层循环比较所有相隔 d 的位置是否相等。如果全部相等说明 d 是循环节直接返回 n // d。它的优点是完全不需要任何算法基础甚至可以手工推算。缺点是当数据量大且字符串字符分布非常均匀时例如全 a 串aaaaaaaaaa每个内层循环都要走到最后才退出整体耗时偏高。但在面试中如果你先写出暴力版再和面试官讨论如何优化到 KMP反而是一种稳妥的沟通策略。2.2 KMP 前缀函数真正的正解KMP 的 Next 数组在字符串周期问题里是核心。这里我不打算展开 KMP 匹配的全过程只讲它和周期的关系。定义前缀函数 pi[i] 表示字符串 S 的子串 S[0..i] 的最长相等真前缀和真后缀的长度。比如s ababab它的 pi 数组为[0, 0, 1, 2, 3, 4]。整个字符串的最后一个 pi 值是 4那么最长 border 的长度就是 4而n - pi[n-1] 6 - 4 2这个 2 就是最小周期。又因为 6 能被 2 整除所以最小循环节就是长度 2 的ab幂次为 3。为什么n - pi[n-1]会等于最小周期原理其实不复杂。如果串的前缀和后缀有长度为 b 的公共部分那么把开头 b 个字符和结尾 b 个字符对齐后中间就空出了一段长度为 n - b 的区域这段区域就是周期。你可以想象成军队绕操场跑步排头跑到某个位置队尾刚好补上两个位置之间的间距就是一个周期的步长。计算前缀函数的递推也不难pi[0] 0从 i 1 开始每次取 j pi[i-1]当 S[i] ! S[j] 时把 j 回退到 pi[j-1]直到 j 为 0 或 S[i] S[j]。如果 S[i] S[j]则 j 加一pi[i] j。这个递推过程其实就是 KMP 失配时的跳转逻辑理解了这一点你就不会再把 next 数组背混了。2.3 滚动哈希另一种优雅的路线如果你把字符串看成一个大整数那比较两个子串是否相等可以用哈希 O(1) 完成。滚动哈希的做法是预处理出整个字符串的前缀哈希和一个对应的幂次数组然后枚举因子 d用哈希快速判断第 i 段和第 i d 段是否相同。以一个质数 base 对整个串做多项式哈希哈希公式为hash[i] (hash[i-1] * base code(S[i])) % mod判断 S 是否由长度为 d 的子串重复得到只需检查整个串的哈希是否等于把长度为 d 的前缀哈希按重复的方式拼接后的哈希。拼接一次的公式是repeat_hash hash[d] * (base^(n-d) base^(n-2d) ... 1) % mod这个公式里的几何级数求和可以预处理幂次数组后 O(1) 算出。实际比较时甚至可以直接对每个分段哈希逐个比较复杂度同样是 O(n * τ(n))但因为每次比较是 O(1)常数很小。不过哈希最大的问题是有碰撞风险。虽然选一个大质数比如 1e97 或 1e99再搭配 64 位无符号整数溢出取模碰撞概率已经低到可以忽略但竞赛中如果数据被特殊构造单哈希仍可能被卡。稳妥做法是双哈希用两个不同的 mod 和 base两个哈希都必须匹配才认定相等。2.4 不同方法怎么选方法时间复杂度空间复杂度适用场景暴力枚举因子O(n * τ(n))O(1)教学演示、小数据规模KMP 前缀函数O(n)O(n)绝大多数竞赛和面试题滚动哈希O(n * τ(n))O(n)需要同时判断多个子串时后缀数组O(n log n)O(n)需要做更复杂的周期分析实际做题时我优先推荐 KMP 前缀函数因为它稳定、好解释、不会碰撞。只有当你需要在一个长字符串里同时查多个子串的幂次关系时滚动哈希才会体现出明显优势因为哈希值可以 O(1) 拿到任意子串的比较结果。3. 多语言代码落地实录3.1 C 语言版POJ 2406 的完整 AC 代码先看最经典的 C 语言实现。POJ 2406 的输入以单独一行.终止每组数据是一个不含空格的字符串你需要在输出时打印最大幂次数。完整代码如下#include stdio.h #include string.h #define MAXN 1000005 char s[MAXN]; int pi[MAXN]; int main(void) { while (scanf(%s, s) ! EOF) { if (s[0] . s[1] \0) break; int n (int)strlen(s); pi[0] 0; for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) j; pi[i] j; } int cycle n - pi[n - 1]; if (n % cycle 0) { printf(%d\n, n / cycle); } else { printf(1\n); } } return 0; }这段代码里scanf(%s, s)能自动跳过空白字符包括换行和空格所以多测输入处理起来非常省心。判断结束条件时我特意加了s[1] \0确保真的只有一个点才结束防止把. 其他字符这种输入误判。cycle的计算是整个程序的核心。注意我优先判断了整除性再输出幂次。如果你把整除判断漏掉直接输出n / cycle遇到abcab这类字符串就会得到错误答案输出一个不存在的幂次。3.2 C 版用 vector 和 string 简化C 的代码基本就是把 C 版本的数组换成vectorint字符串换成std::string更方便处理动态长度。核心求解函数可以单独封装#include iostream #include vector #include string using namespace std; int max_power(const string s) { int n (int)s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) { j pi[j - 1]; } if (s[i] s[j]) j; pi[i] j; } int cycle n - pi[n - 1]; if (n % cycle 0) return n / cycle; return 1; } int main() { string s; while (cin s) { if (s .) break; cout max_power(s) \n; } return 0; }这里我使用的pi[i - 1]表示前缀函数也就是最长 border 长度而不是 KMP 匹配时常用的失配指针。两者的区别在于失配指针有时会保存pi[i]对应的下标这个下标等于pi[i]的值而前缀函数保存的是长度。只要你在比较时用的是长度而非下标代码就不会出问题。3.3 Python 版写起来最短但要注意性能Python 实现和 C 在逻辑上完全一致只是要注意防止在大数据量下超时。用列表存储 pi 数组循环内部尽量减少属性访问能提升不少速度def max_power(s: str) - int: n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and s[i] ! s[j]: j pi[j - 1] if s[i] s[j]: j 1 pi[i] j cycle n - pi[-1] if n % cycle 0: return n // cycle return 1在 OJ 上跑 Python 版时如果遇到 n 为 1e6 级别的输入虽然 KMP 本身是线性的但 Python 的大循环还是会有常数开销。一个常见的优化是用 PyPy 提交或者把读入从input()改成sys.stdin.buffer.read().split()一次性读入所有字符串再逐条处理能显著减少 I/O 时间。3.4 Java / C# / JavaScript 的要点Java 的String.charAt()在循环里反复调用会有一些性能损耗可以先转成字符数组再处理计算前缀函数时用char[] arr s.toCharArray()之后arr[i]的访问比s.charAt(i)更快。C# 则要注意字符串是不可变类型频繁做Substring是反面教材这里只用索引访问字符不需要拼接所以问题不大。JavaScript 版跑在 Node.js 上时要注意s[i]在字符串上是可用的但s.length很大时递归不可取用普通for循环即可。函数式写法或者正则匹配在这种问题上虽然简短但性能远不如显式循环。3.5 输入解析与多测用例处理字符串乘方题目中输入格式常见两种第一种是像 POJ 2406 那样每行一个字符串单独一行.表示结束第二种是像 HDU 1358 那样给一个 n 和一个字符串让找出所有前缀中能由某个循环节重复得到的位置。第二种情况需要你在构造 pi 数组的同时检查每个位置的前缀。核心判断是(i 1) % cycle 0其中i 1是当前前缀长度。一旦满足条件说明前缀 S[0..i] 是一个完整的乘方串循环节长度是 cycle幂次是(i 1) / cycle。把这一判断放在求 pi 的循环里同步做就不会额外增加时间复杂度。4. 沉迷踩坑常见问题与排查思路4.1 next 数组定义搞混这是新手最容易懵的地方。同样是“next 数组”有的教程用next[0] -1表示失配指针的起点有的直接用前缀函数。如果把这两种实现混着用最典型的问题就是计算cycle时多 1 或者少 1。我自己的习惯是统一用前缀函数的定义pi[0] 0计算出的pi[i]永远是长度。这样cycle n - pi[n-1]的语义非常清楚它是整个字符串的最小周期长度。如果你用的是next[0] -1的版本那么对应关系会变成cycle n - (next[n] 1)这个next[n]往往存储在数组末尾的下一个位置。别去硬背哪种写法更合理挑一种顺手的然后每次都用它代码就不容易错。4.2 边界条件空串、单字符、全相同字符边界条件绝对是判题机最爱的陷阱。先看空串有些题目的输入可能包含空行如果你直接读入后调用求 pi 的逻辑n - pi[-1]会访问不存在的元素。所以进入主逻辑前必须判断n 0此时没有幂次可谈题目通常也不会给出这种数据但健壮性处理不能少。再看单字符a它的 n 1pi[0] 0cycle 11 % 1 0输出 1 或者 1 都没问题。但有的同学会在n 1时产生疑惑它算不算最小周期串严格来说任何字符串都可以看作自身的一次乘方所以答案是 1。全相同字符aaaa是最好的测试数据pi 数组是[0, 1, 2, 3]cycle 1整除成立答案是 4。如果这个数据你的代码输出不了 4说明 pi 递推里的小等号可能写漏了。4.3 大小写、空白与隐藏字符有些题目会要求忽略大小写后判断字符串是否为乘方串比如给你AbAbAb让你大小写不敏感地返回 3。解决思路很简单先对字符串做一次统一大小写处理变成小写再跑 KMP。这里必须明确一点算法层面不能依赖运行环境的默认配置也不能指望数据库的排序规则来帮忙。你必须在自己的代码里显式调用tolower或toLowerCase。空白字符也是隐藏大坑。如果字符串是从文件或者网络中读取的可能带换行符\n或回车符\r。C 语言里scanf(%s, s)会自动处理这部分但如果你用fgets记得用strcspn把末尾换行去掉。Python 的input()会自动去掉末尾换行但不会去掉中间的空格。4.4 哈希冲突与取模选质数用哈希法时质数的选择经常被忽视。base 可以取一个奇数比如 13331、131 等mod 最好取一个大质数比如 1e97、1e99。如果你的字符串只包含小写字母base 选择 131 这类数值后碰撞概率很小但如果包含任意 ASCII 字符建议把 base 取大一些或者直接用无符号 64 位整数自然溢出取模。自然溢出取模的本质是 mod 2^64这在实际中运行极快但理论上它是合数。在竞赛中被精心构造的数据确实可能卡掉单哈希所以稳妥的工程方案是双哈希准备两组 base 和 mod只有两个哈希都匹配时才认为子串相等。代价是计算量翻倍但在当前算力下完全可接受。4.5 大字符串场景的内存与 IO当字符串长度达到 1e6 或 1e7 级别内存和 IO 就成了主要瓶颈。C 语言的全局数组char s[MAXN]能轻松容纳 1e6 个字符但如果长度来到 1e7就要考虑malloc动态分配。pi 数组的int类型在 4 字节下1e7 大约占 40MB内存紧张时可以把int换成short但要注意 n 不能太大。IO 方面C 语言可以用scanfC 建议关闭同步ios::sync_with_stdio(false)Python 一定要用sys.stdin.buffer.read()。这些 IO 优化在你只需要跑一次算法时效果不明显但在多测用例中能差出几倍时间。5. 字符串乘方在真实场景里的影子5.1 文本压缩与字典构造字符串乘方问题和文本压缩之间有直接关系。如果一段文本由多段完全相同的子串拼接而成那我们可以只存储一份子串和重复次数这就是最简单的字典压缩思想。实际工程中的 LZW 压缩、zip 压缩算法里会大量用到字符串匹配和周期检测只不过实现细节更复杂。在数据备份和日志去重领域这种思路更实用。比如若干台设备上报的日志每条日志开头都包含相同的设备标识和时间戳通过检测这段公共前缀的“循环节”可以显著减少存储量。我之前在做一个日志采集平台时就遇到过磁盘写满的问题后来对日志按前缀做了乘方聚合存储量直接降了一个数量级。5.2 生物信息学中的串联重复检测DNA 和蛋白质序列里经常出现串联重复结构比如ATATAT这样由短片段 repeated 的序列。这种重复与许多遗传疾病相关所以检测一个长序列中是否存在某个片段的多次串联是基因数据分析的常见需求。生物信息学里的序列长度动辄上亿个碱基KMP 前缀函数这种 O(n) 算法在这里就很有优势。更进阶的题目还会结合滑动窗口对每个长度为 m 的子序列判断它是否为乘方串这就完全是把字符串乘方问题放到大数据场景里重新包装了。5.3 代码审计重复代码块挖掘在工程代码里如果一段代码被原样复制粘贴了很多次我们可以把它看作某个“代码块”的乘方结构。对代码文本做预处理去掉空格和注释后再检测乘方关系能快速找到重复度最高的模块。这类工具在很多大厂内部的代码质量平台里都有实现底层核心就是字符串周期检测。从复杂度上分析一个包含 n 个字符的代码文件跑一遍 KMP 前缀函数 O(n) 就能找到所有能被短块重复覆盖的连续区间。相比之下用暴力比较两两代码块的做法是 O(n^2)在大型代码仓库上根本跑不动。5.4 变体题带权字符、多次询问、逆序性质刷题时你会碰到很多字符串乘方的变体。比如题目给一个长度为 n 的字符串其中只包含r、g、b三种字符再给一个值 m让你统计有多少个长度不小于 m 的子串是乘方串。这类题目通常要结合滑窗和哈希先枚举循环节长度 d用滚动哈希快速比较每段是否相等再统计满足长度条件的数量。还有一种常见变体是结合回文。因为如果 S T^k那么 S 的逆序reverse(S)等于reverse(T)^k乘方关系在反转操作下保持成立。利用这个性质可以快速判断一个字符串和它的逆序是否存在相同的循环节进而解决一些复杂的双串匹配问题。6. 踩完这些坑之后我的实操建议6.1 不要死记模板理解 border 才是关键以前我备考时也背过 KMP 模板但一到变体题还是会卡住。后来我把 Next 数组彻底理解成“最长 border 长度”之后很多题就突然通了。字符串的 border 就是前缀和后缀相同的部分周期问题的本质就是利用 border 来说事。你只要记住最小周期等于 n 减去整个字符串的 border 长度然后判断是否能整除。这一条规则能覆盖八成字符串周期题。6.2 遇到类似题目先写暴力再优化竞赛里有句经验先写个正确的暴力程序再拿它和数据生成器对拍用来验证高效算法的正确性。字符串乘方问题也适合这么做。先写 O(n * τ(n)) 的因子枚举版本再写 KMP 版本然后构造随机小串和大串对比输出。这个方法能帮你快速发现整除判断、下标偏移这类隐蔽 bug。6.3 最小循环节提取的一个调试技巧如果你需要用循环节去还原最小重复子串可以拿到cycle长度后直接取原串前cycle个字符作为 T。但这只能在你已经确认整除条件成立时才有效否则前 cycle 个字符并不是真正的循环节。我在调试时经常用一个工具函数专门打印出 pi 数组和推导出的周期值这样能直观看到算法走到了哪一步也方便对比不同字符串下 border 长度的变化。字符串乘方看似是个小题但背后牵连着字符串哈希、前缀函数、周期定理这些核心知识点。把它彻底吃透你在处理字符串匹配、压缩算法、甚至代码分析任务时都会比别人多一层底层理解。我自己在这道题上踩过的坑就是最好的教学案例先搞清楚数学定义再选择合适的算法实现最后用边界数据验证这条路径几乎适用于所有算法题。
