1. 从一道经典题看字符串循环同构的本质第一次遇到“给一堆字符串问有多少种本质不同的循环同构串”这类问题很多人第一反应是暴力枚举每个串的所有循环移位然后塞进哈希表去重。思路没错但复杂度直接爆炸——假设单个串长度是 n枚举所有移位就是 O(n)每个移位还要做一次长度为 n 的比较或哈希整体轻松飙到 O(n²)。如果串的数量再乘上去基本就告别通过测试了。这道题的核心其实是在问一个更底层的问题两个字符串在循环移位意义下是否相等换句话说把字符串看成一个首尾相接的环从不同位置剪开得到的线性串是否可能一样。比如abcd循环移位能得到bcda、cdab、dabc这四个串在“循环同构”的意义下是同一个东西。题目要求统计的就是这种等价类的数量。解决这类问题的标准武器叫最小表示法Minimal Representation有时也叫最小循环表示。它的目标很明确对于一个给定的字符串在它所有的循环移位中找到字典序最小的那一个并用它作为这个等价类的“代表元”。只要两个串的最小表示相同它们就属于同一个循环同构类。这样一来问题就从“两两比较所有移位”变成了“每个串只算一次最小表示然后对代表元去重”复杂度直接降到 O(n) 级别。我第一次接触这个思路时觉得它有点像给每个等价类发一张“身份证”——不管你这个环从哪儿剪开只要把它转到一个固定的、最小的姿态大家就能一眼认出是不是同一家人。这个“转到最小姿态”的过程就是最小表示法要干的事。提示最小表示法处理的是循环同构不是普通的字符串相等。判断两个串是否循环同构最稳妥的方式就是比较它们的最小表示是否一致。下面我会从最朴素的暴力做法讲起一步步推导到 O(n) 的最小表示算法再把这道题的完整解题链路拆开包括去重时容易踩的坑、哈希与最小表示的配合方式以及我在实际写题过程中总结的几个能省时间的细节。2. 暴力枚举为什么在数据量大时必然翻车2.1 最直观的做法与它的代价拿到一个字符串 s长度记为 n。最直接的想法是生成它的所有循环移位一共 n 个每个长度也是 n。然后从这 n 个串里挑出字典序最小的那个作为代表元。生成所有移位本身就要 O(n²) 的时间——因为你要复制 n 次每次复制 n 个字符。如果只是生成还好问题是生成之后还要比较。假设你用最朴素的逐个字符比较来选最小每比较两个串最坏要 O(n)n 个串两两比较就是 O(n²) 次比较总复杂度 O(n³)。即便你用排序把比较次数降到 O(n log n)每次比较仍是 O(n)整体还是 O(n² log n)。对于长度只有几十的串这点开销无所谓。但题目里字符串数量可能上千单个长度也可能上千O(n²) 甚至 O(n³) 的算法在时间限制面前基本没有生还的可能。我早期写这类题时就吃过这个亏本地小数据跑得飞快一提交就超时回头一算复杂度才发现问题。2.2 一个容易被忽略的细节重复移位还有一个隐蔽的坑。如果字符串本身存在周期性比如abab它的循环移位只有abab和baba两种不同的形态但暴力枚举会老老实实生成 4 个串。这本身不算错但会让你在去重时产生冗余操作。更麻烦的是如果你用“生成所有移位再排序取第一个”的策略遇到周期串时排序结果里会出现多个相同的最小串虽然不影响最终取到的最小值但会浪费计算资源。真正的问题在于暴力法没有利用字符串内部的结构信息。它把每个移位都当成一个全新的、独立的串来处理完全无视了相邻移位之间只差一个字符移动这个事实。最小表示法的精妙之处恰恰在于它利用了这种“滑动”关系用两个指针在原串上跑避免真正去构造那些移位串。2.3 从暴力到优化的思维转折要优化先得想清楚我们到底在比较什么比较两个移位本质上是在比较从两个不同起点出发、沿着环走一圈得到的字符序列。既然它们走的是同一个环那么比较过程中一旦发现某个位置字符不同就能立刻判断出哪个起点的字典序更小。更进一步如果从起点 i 出发的序列和从起点 j 出发的序列在前 k 个字符都相同第 k1 个字符不同那么我们不仅能判断 i 和 j 的优劣还能顺带排除掉一批起点。这个“顺带排除”就是最小表示法能把复杂度压到 O(n) 的关键。具体怎么排除下一节会详细拆。3. 最小表示法的双指针推导与边界处理3.1 算法骨架两个指针在环上赛跑最小表示法的经典实现用两个指针 i 和 j初始时 i 0j 1再用一个变量 k 表示当前比较到了第几个字符也就是两个起点出发的序列已经匹配了多长。每一轮比较 s[(ik) % n] 和 s[(jk) % n]如果相等k 加一继续往后比。如果 s[(ik) % n] s[(jk) % n]说明从 i 出发的序列在当前位置输给了从 j 出发的序列。此时 i 需要往后跳跳过一段已经确定不可能是最小起点的位置。如果 s[(ik) % n] s[(jk) % n]对称地j 往后跳。关键在于“跳多少”。假设在位置 k 处 i 输给了 j那么从 i 到 ik 这一段的任意一个位置作为起点都不可能比从 j 出发更优。原因是从 i1 出发的序列相当于从 i 出发的序列去掉首字符再拼接而它在与 j 的比较中同样会在某个位置落后。严谨的证明可以用反证法但直观理解就是——i 已经在一个更长的前缀上输给了 j它的所有“后缀起点”继承了这个劣势。所以 i 直接跳到 i k 1。同理j 输的时候跳到 j k 1。跳完之后如果 i 和 j 撞上了就把其中一个再加一保证两个指针不重合。3.2 为什么跳过的位置一定不是最小起点这一步是整个算法正确性的核心值得多花点笔墨说清楚。假设从 i 出发和从 j 出发的序列前 k 个字符完全相同第 k1 个字符满足 s[ik] s[jk]下标模 n。现在考虑任意一个位于 i 和 ik 之间的起点 i即 i i ≤ ik。从 i 出发的序列它的前 (ik-i) 个字符恰好等于从 i 出发序列的对应片段也就是和从 j 出发序列的对应片段相同。而再往后比从 i 出发的序列会走到 ik 这个位置此时它对应的字符是 s[ik]而从 j 出发的序列在相同偏移处对应的字符是 s[jk]这里需要稍微绕一下但结论成立。由于 s[ik] s[jk]从 i 出发的序列同样会在这一轮比较中输给从 j 出发的序列。因此i 到 ik 之间的所有起点都可以安全跳过。这就是“跳 k1 步”而不是“跳 1 步”的理论依据。理解了这一点你就明白为什么这个看似简单的跳跃能让总比较次数降到 O(n)——因为 i 和 j 各自最多走 n 步k 的总增长也是 O(n) 级别。3.3 边界情况周期串与指针重合实际写代码时有几个边界必须处理干净。第一当 i 和 j 重合时需要把其中一个指针往后挪一位否则会陷入自己和自己比较的死循环。通常的做法是if (i j) j;。第二k 不能无限增长。当 k 达到 n 时说明两个起点出发的序列完全一样这意味着字符串是周期串且 i 和 j 属于同一个等价类。此时直接跳出循环即可因为再比下去也没有意义。第三取模运算要小心。(i k) % n和(j k) % n在 k 较大时会绕回开头这是环结构的体现不能省略取模。第四最终返回的最小起点是min(i, j)。因为循环结束时两个指针中较小的那个对应字典序最小的移位起点。下面是一个可以直接套用的最小表示函数模板int minimalRepresentation(const string s) { int n s.size(); int i 0, j 1, k 0; while (i n j n k n) { char a s[(i k) % n]; char b s[(j k) % n]; if (a b) { k; } else if (a b) { i i k 1; if (i j) i; k 0; } else { j j k 1; if (i j) j; k 0; } } return min(i, j); }拿到起点之后从该起点出发绕一圈构造出的字符串就是这个串的最小表示。实际去重时你甚至不需要真的构造出最小表示串只需要记录起点和原串的某种哈希或者直接把最小表示串截出来塞进集合。4. 把最小表示法用到“统计不同循环同构串数量”上4.1 整体解题链路回到题目本身给若干个字符串统计有多少个本质不同的循环同构类。完整的处理流程是这样的读入所有字符串。对每个字符串调用最小表示法求出最小起点。从最小起点出发构造出该串的最小表示字符串。把所有最小表示字符串放入一个集合set 或 unordered_set去重。集合的大小就是答案。这个链路看起来简单但每一步都有值得推敲的地方。比如第 3 步构造最小表示串时如果直接做字符串拼接会产生额外的 O(n) 空间和时间开销。对于数据量大的情况可以考虑用哈希代替完整字符串但哈希有碰撞风险需要权衡。4.2 去重时用 set 还是 unordered_set这是一个很实际的选择问题。setstring底层是红黑树插入和查询都是 O(log m) 次字符串比较m 是集合大小。每次比较最坏 O(n)。整体复杂度 O(m log m · n)。优点是稳定、无碰撞、代码简单。unordered_setstring底层是哈希表平均插入查询 O(1) 次哈希计算每次哈希 O(n)。整体平均 O(m · n)。优点是平均更快缺点是遇到哈希碰撞或者被针对构造的数据时可能退化而且需要自己写哈希函数标准库对 string 有默认哈希但某些环境下可能被卡。我的经验是如果题目没有明确卡哈希用setstring最省心代码短、不易出错。如果数据量确实很大比如上万个长度上千的串再考虑unordered_set并配一个自定义的、带随机种子的哈希函数。4.3 一个能省一半时间的优化只存哈希值如果你对哈希碰撞的容忍度较高或者可以用双哈希把碰撞概率压到极低那么完全没必要把最小表示串完整存下来。只需要对每个串的最小表示计算一个哈希值然后把哈希值放进集合去重即可。这样做的好处是集合里存的是整数比较和存储开销都远小于字符串。坏处是理论上存在碰撞可能两个不同的最小表示可能哈希到同一个值导致答案偏小。为了降低风险可以用双哈希两个不同的模数和基数把碰撞概率降到可以忽略的程度。具体做法是先求出最小起点 pos然后从 pos 开始绕一圈边遍历边计算哈希。注意因为是从环上某点出发走 n 步遍历时下标要取模。// 双哈希示例模数和基数仅为示意实际可自行选择 const long long MOD1 1000000007, MOD2 1000000009; const long long BASE 131; pairlong long, long long getHash(const string s, int pos) { int n s.size(); long long h1 0, h2 0; for (int i 0; i n; i) { char c s[(pos i) % n]; h1 (h1 * BASE c) % MOD1; h2 (h2 * BASE c) % MOD2; } return {h1, h2}; }把pair放进set或unordered_set即可。这个优化在字符串很长时效果非常明显。5. 实测中容易踩的坑与调试经验5.1 指针跳跃后忘记重置 k这是新手写最小表示法时最高频的错误。在 i 或 j 跳跃之后k 必须重置为 0因为新的起点对之间还没有进行任何比较。如果忘记重置k 会保留之前的值导致后续比较从错误的偏移开始结果完全错乱。我当初调这个 bug 时打印了每一轮的 i、j、k 才定位到问题。建议你在第一次实现时也加上调试输出确认跳跃逻辑符合预期后再删掉。5.2 周期串导致的死循环对于像aaaa这样的全同字符串i 和 j 的比较会一直相等k 不断增长。如果没有k n这个终止条件循环永远不会结束。加上这个条件后k 达到 n 时退出返回 min(i, j)结果是正确的。另一个相关的情况是ababab这种短周期串。算法同样能正确处理但你要确保指针重合时的i或j逻辑到位否则可能两个指针一直相等循环空转。5.3 下标取模与字符串拼接的顺序构造最小表示串时最容易写错的就是下标。正确的顺序是从 pos 开始依次取 s[pos % n]、s[(pos1) % n]、……、s[(posn-1) % n]。如果你先对 pos 取模再递增逻辑上没问题但如果先递增再取模可能会漏掉或多算字符。建议统一写成s[(pos i) % n]的形式i 从 0 到 n-1这样最不容易出错。5.4 多组输入的清空问题如果题目是多组测试数据每一组之间一定要把集合清空。我见过有人用全局集合忘记清导致上一组的结果污染下一组答案莫名其妙偏大。用局部变量声明集合是最稳妥的做法作用域结束自动销毁。5.5 空串与单字符串的特殊处理虽然大多数题目不会给空串但单字符串是常见的。长度为 1 时最小表示就是它自己最小起点是 0。算法本身能处理但如果你在构造最小表示串时用了某些假设 n ≥ 2 的优化就可能出问题。保险起见对 n 1 的情况可以直接返回原串。6. 从这道题延伸出去最小表示法的适用场景最小表示法不只是用来做这道统计题。凡是涉及“循环同构判断”的场景它都能派上用场。比如判断两个字符串是否互为循环移位直接比较它们的最小表示即可比暴力枚举所有移位高效得多。再比如在某些字符串匹配问题中需要把模式串和文本串都转成最小表示后再做匹配可以避免因起始位置不同而漏匹配。还有一个常见的变体是“最大表示法”思路完全对称只需要把比较时的方向反过来。有些题目要求找字典序最大的循环移位改一下符号就行。另外最小表示法和 KMP、后缀数组等字符串工具并不是互斥的。有些复杂问题会先用最小表示法把环状结构“拉直”再用 KMP 做线性匹配组合起来能解决不少看起来棘手的场景。我在实际写题时的一个体会是遇到环状字符串相关的问题先想想能不能用最小表示法把环破开成链。很多时候破环之后问题就退化成普通的线性字符串问题难度直接降一个档次。这个思路值得你在遇到新题时优先考虑。最后分享一个调试小技巧当你怀疑最小表示法写错时可以写一个暴力版本随机生成小字符串两个版本对拍。对拍几百组之后基本能覆盖所有边界情况比肉眼查代码高效得多。