★ FEATURED ARTICLE 1. 从一道经典题看字符串最小表示的实战价值字符串处理里有一类问题特别有意思给你一堆字符串每个字符串都被认为是首尾相连的循环结构问你有多少个本质不同的字符串。所谓本质不同就是两个字符串不管怎么旋转都没法变得一模一样。这类问题在数据清洗、DNA序列分析、循环日志去重等场景里非常常见。我第一次遇到这类需求是在处理一批传感器采集的周期性信号编码当时用最朴素的两两比较加暴力旋转数据量一上来直接卡死后来才意识到这背后有一套成熟的算法工具——字符串最小表示法。这篇文章围绕一个经典题目展开给定若干个字符串每个字符串代表一个循环串要求统计其中本质不同的字符串个数。核心关键词是字符串最小表示配套的技术点包括循环同构判定、最小表示法算法实现、字符串去重。我会从问题本质讲起把最小表示法的原理、实现细节、参数选择、常见坑点全部拆开揉碎让你看完就能直接上手写代码解决同类问题。不管你是刚接触字符串算法的新手还是想复习一下经典套路的进阶选手这篇内容都能给你提供可直接参考的完整方案。先把这个问题的核心逻辑说清楚。假设有两个字符串一个叫A一个叫B。如果A可以通过若干次循环移位变成B那它们就属于同一个“循环同构类”。比如“abcd”旋转一次得到“bcda”再旋转得到“cdab”再旋转得到“dabc”这四个字符串本质上是同一个东西。现在给你N个字符串每个都可能是任意长度你要数出这里面有多少个不同的循环同构类。最直接的想法是对每个字符串找出它所有旋转结果中字典序最小的那个把它当作这个类的“代表元”然后对所有代表元去重剩下的数量就是答案。这个思路是对的而“找出字典序最小的旋转结果”这件事就是最小表示法要解决的问题。为什么不能暴力假设字符串长度是L每个字符串有L种旋转每种旋转比较需要O(L)时间单个字符串就是O(L²)。如果N个字符串总长度达到10⁶级别暴力做法直接超时。最小表示法可以把单个字符串的处理降到O(L)整体复杂度O(总长度)这就是它的核心价值。下面我会从算法原理、代码实现、去重策略、边界处理几个维度逐一展开中间穿插我在实际使用中踩过的坑和总结的技巧。2. 最小表示法到底在做什么原理拆解与方案选型2.1 循环同构的本质与代表元思想要理解最小表示法先得理解“循环同构”这个概念。一个长度为L的字符串S它的循环同构串一共有L个可能有重复比如“aaaa”的L个旋转都一样。这L个串构成一个等价类。如果我们能从每个等价类里选出一个唯一的代表元那么统计不同等价类的数量就变成了统计不同代表元的数量。选谁当代表元最自然的选择是字典序最小的那个。字典序比较规则很简单从左到右逐字符比较第一个不同字符处字符小的那个串更小如果一直比到结尾都相同则长度短的更小但循环同构串长度都一样所以这条用不上。选最小字典序旋转作为代表元有两个好处一是唯一性有保证同一个等价类的最小表示一定相同二是计算起来有高效算法。这里有个容易混淆的点最小表示和最大表示是对称的有些场景下选最大表示也可以但本文统一用最小表示。另外要注意如果字符串本身有周期性比如“abab”它的不同旋转只有“abab”和“baba”两个但按长度算有4个旋转。最小表示法依然能正确处理因为它找的是所有旋转中字典序最小的那个重复的旋转不会影响结果。2.2 暴力法为什么不够用复杂度账要算清楚在讲高效算法之前先看看暴力法到底慢在哪里。暴力法的流程是枚举起始位置i从0到L-1对于每个i构造旋转串S[i:]S[:i]然后和当前记录的最小串比较。构造旋转串需要O(L)比较需要O(L)所以单个起始位置是O(L)总共L个起始位置就是O(L²)。假设总共有N个字符串平均长度L总长度MN×L。暴力法总复杂度是O(N×L²)O(M×L)。如果M10⁶L10³那就是10⁹级别的操作在主流评测环境里基本必超时。而最小表示法是O(M)差距是L倍。当L达到几千甚至几万时这个差距就是致命的。所以只要数据规模稍微大一点就必须用最小表示法。我当初处理传感器数据时单个序列长度大概2000数量5000条总长度10⁷。暴力法跑一次要几十秒换成最小表示法之后直接降到几百毫秒。这个提升不是一点半点而是量级上的差异。2.3 最小表示法的核心思想双指针滑动比较最小表示法的经典实现用两个指针i和j分别指向两个候选的起始位置然后用一个变量k表示当前比较到的偏移量。初始时i0j1k0。比较S[(ik)%L]和S[(jk)%L]如果相等k加1继续比较下一个字符。如果S[(ik)%L] S[(jk)%L]说明以i开头的旋转串不如以j开头的i可以直接跳到ik1。如果S[(ik)%L] S[(jk)%L]说明以j开头的旋转串不如以i开头的j可以直接跳到jk1。如果跳完之后i和j相等让j加1保证两个指针不重合。当k达到L或者i或j超过L时循环结束min(i,j)就是最小表示的起始位置。这个算法的精妙之处在于“跳跃”当发现以i开头的串在偏移k处比以j开头的串大时不仅i这个位置不行从i到ik这些位置作为起始都不行。为什么呢因为以i1开头的串相当于把以i开头的串去掉第一个字符而由于前k个字符和以j开头的串相同以i1开头的串在偏移k-1处依然会输给以j1开头的串。这个性质保证了跳跃的正确性也是算法能做到O(L)的关键。2.4 为什么选择最小表示而不是其他方案解决循环同构去重除了最小表示法还有几种思路。一种是哈希法对每个字符串的所有旋转计算哈希值取最小的哈希作为代表。这种做法期望复杂度也是O(L)但存在哈希冲突风险而且需要处理双哈希或者大模数实现起来更繁琐。另一种是后缀数组或后缀自动机能解决更复杂的循环同构问题但代码量大、常数高对于本题这种“只需要最小表示”的场景属于杀鸡用牛刀。最小表示法的优势在于代码短、常数小、逻辑直观、无冲突风险、复杂度严格O(L)。它不需要任何额外数据结构只需要原字符串和一个循环比较过程。对于竞赛场景和工程场景都非常友好。我个人的选择标准是如果只需要判定循环同构或者找最小表示优先用最小表示法如果需要处理更复杂的循环子串匹配再考虑后缀结构。3. 最小表示法代码实现与关键细节3.1 核心代码模板与逐行解读先给出最小表示法的标准实现然后逐行解释每个细节。int minRepresentation(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); }这段代码看起来简单但每一行都有讲究。i和j是两个候选起始位置k是当前比较的偏移量。循环条件是三个指针都小于n因为一旦某个指针达到n说明它已经不可能成为最小表示的起点了起始位置只能在0到n-1之间。当s[(ik)%n] s[(jk)%n]时说明当前偏移处两个候选串相同需要继续往后比所以k。当s[(ik)%n] s[(jk)%n]时说明以i开头的串在偏移k处输给了以j开头的串那么i到ik这些起始位置都不可能是最小表示直接跳到ik1。跳完之后如果i和j重合需要把i再往后挪一位保证两个指针始终指向不同的候选。同理处理小于的情况。最后返回min(i, j)因为循环结束时可能有一个指针越界另一个指针就是答案。注意这里返回的是起始位置不是最小表示串本身。如果需要最小表示串可以用这个位置构造s.substr(pos) s.substr(0, pos)。3.2 取模操作的性能陷阱与优化上面的代码用了(ik)%n来取字符这在逻辑上没问题但取模运算是相对昂贵的操作。在数据量大的时候频繁取模会成为性能瓶颈。一个常见的优化是拆开循环避免取模int minRepresentation(const string s) { int n s.size(); int i 0, j 1, k 0; while (i n j n k n) { char a (i k n) ? s[i k] : s[i k - n]; char b (j k n) ? s[j k] : 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); }用条件判断代替取模在大多数平台上能带来明显的性能提升。我实测过在总长度10⁷的数据上优化后的版本比取模版本快大约30%到40%。这个技巧在处理大规模字符串时非常值得采用。另一个优化思路是把字符串复制一份接在后面这样就不需要取模了直接用s[ik]和s[jk]访问。但这样会额外消耗一倍内存对于内存敏感的场景需要权衡。如果内存充足复制拼接的做法代码更简洁性能也不错。3.3 边界情况处理空串、单字符与全同字符最小表示法有几个边界情况需要特别注意。第一是空串长度为0的字符串没有最小表示需要在调用前单独处理。第二是单字符字符串长度为1时最小表示就是它自己起始位置为0算法也能正确处理但可以提前返回避免进入循环。第三是全同字符字符串比如“aaaa”这种情况下所有旋转都一样算法会在k达到n时结束返回的起始位置是0结果正确。还有一个容易忽略的边界当字符串长度很大但实际周期很小时比如“abababab...”算法依然能在O(L)时间内完成不会因为周期小而变慢。这是因为k最多增加到n而每次跳跃至少让i或j前进1总操作次数是O(n)的。我在实际使用中遇到过一个坑如果字符串长度是0直接调用最小表示法会导致数组越界或者死循环。所以工程代码里一定要在调用前检查空串。另外如果字符串长度是1虽然算法能跑但可以提前返回0省去不必要的循环开销。3.4 最小表示法的正确性证明思路虽然本文重点在实操但理解正确性证明能帮你更好地记住算法。核心证明分两步第一算法不会错过真正的最小表示起始位置第二算法的时间复杂度是O(n)。第一步的证明依赖于“跳跃”的正确性。假设当前比较到偏移k时以i开头的串大于以j开头的串。那么对于任意t在0到k之间以it开头的串在偏移k-t处会输给以jt开头的串。这是因为两个串的前k个字符相同去掉前t个字符后相对关系保持不变。所以i到ik这些位置都不可能是最小表示可以安全跳过。第二步的证明依赖于i和j的单调性。每次跳跃至少让i或j增加1而k在跳跃后重置为0。i和j最多增加到nk最多增加到n所以总操作次数是O(n)。这个证明思路在面试中经常被问到理解了对你有好处。4. 完整解题流程从输入到输出4.1 整体算法框架设计回到原始问题给定N个字符串统计本质不同的循环同构串个数。整体框架分三步读入N个字符串。对每个字符串计算其最小表示的起始位置构造最小表示串。把所有最小表示串放入一个集合去重集合大小就是答案。这个框架看起来简单但每一步都有细节。第一步读入时要注意字符串可能包含空格吗通常这类题目字符串只包含小写字母不含空格用cin s即可。如果包含空格需要用getline。第二步构造最小表示串时可以用substr拼接也可以直接比较起始位置而不构造新串。第三步去重可以用setstring或者排序后去重。如果N很大用setstring可能会因为字符串比较和内存分配而变慢。一个更高效的做法是把所有最小表示串存入vectorstring然后排序再用unique去重。排序的复杂度是O(M log N)其中M是总长度N是字符串个数。对于大多数场景这个做法比set更快因为set的每次插入都有树调整开销。4.2 字符串去重策略对比与选择去重策略的选择取决于数据规模和具体需求。下面用一个表格对比几种常见方案方案时间复杂度空间复杂度适用场景注意事项setO(M log N)O(M)数据量中等代码简洁每次插入有树调整开销排序uniqueO(M log N)O(M)数据量大追求性能需要额外排序步骤哈希表O(M)期望O(M)数据量极大允许冲突风险需要处理哈希冲突Trie树O(M)O(M×字符集)字符串前缀重复多内存消耗较大我个人的选择习惯是如果总长度在10⁶以内直接用setstring代码最短不容易出错。如果总长度超过10⁶改用排序unique性能更稳。哈希表虽然期望复杂度低但冲突处理麻烦除非有特殊需求一般不优先考虑。还有一个细节如果两个字符串长度不同它们一定不属于同一个循环同构类因为循环同构不改变长度。所以可以在去重前先按长度分组只对同长度的字符串做最小表示和去重。这个优化在字符串长度分布分散时能显著减少比较次数。4.3 完整代码实现与注释下面给出完整的解题代码包含输入处理、最小表示计算、去重和输出。#include bits/stdc.h using namespace std; int minRepresentation(const string s) { int n s.size(); if (n 0) return 0; if (n 1) return 0; int i 0, j 1, k 0; while (i n j n k n) { char a (i k n) ? s[i k] : s[i k - n]; char b (j k n) ? s[j k] : 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); } string getMinString(const string s) { int pos minRepresentation(s); return s.substr(pos) s.substr(0, pos); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n) { setstring st; for (int i 0; i n; i) { string s; cin s; st.insert(getMinString(s)); } cout st.size() \n; } return 0; }这段代码有几个值得说明的地方。第一用了ios::sync_with_stdio(false)和cin.tie(nullptr)来加速输入输出这在数据量大时很重要。第二minRepresentation里对空串和单字符做了提前返回避免边界问题。第三getMinString通过substr拼接构造最小表示串逻辑清晰。第四用setstring自动去重代码简洁。如果追求更高性能可以把set换成vector加排序去重vectorstring vec; for (int i 0; i n; i) { string s; cin s; vec.push_back(getMinString(s)); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); cout vec.size() \n;两种写法结果一样性能上排序版本通常更快尤其是在N较大时。4.4 复杂度分析与数据规模适配完整算法的时间复杂度是O(M N log N)其中M是总字符数N是字符串个数。最小表示部分对每个字符串是O(L)总共O(M)。去重部分如果用排序是O(N log N)次字符串比较每次比较最坏O(L)所以是O(M log N)。如果用set每次插入是O(log N)次比较总共也是O(M log N)。空间复杂度是O(M)主要是存储所有最小表示串的开销。如果内存紧张可以在线处理每读入一个字符串就计算最小表示并插入集合不需要保存原始字符串。这样空间就是O(不同最小表示串的总长度)通常比O(M)小。对于数据规模如果总长度在10⁶以内上面的代码都能轻松通过。如果总长度达到10⁷建议用排序去重加输入输出优化。如果总长度超过10⁸可能需要考虑更紧凑的字符串存储方式比如用字符数组代替string或者用哈希值代替完整字符串去重。5. 常见问题与排查技巧实录5.1 最小表示法写错的典型症状最小表示法代码短但写错的方式五花八门。我总结了几种典型症状和对应对策症状一结果偏大或偏小。通常是因为跳跃时没有正确处理i j的情况。当i跳到ik1后如果等于j必须让i再加1否则两个指针重合会导致比较逻辑混乱。同理j跳到jk1后如果等于i也要让j加1。症状二死循环。常见原因是k在跳跃后没有重置为0。每次跳跃后必须把k归零因为新的候选起始位置需要从头开始比较。另一个原因是循环条件写错比如漏了k n导致k无限增长。症状三数组越界。如果用取模访问一般不会越界。但如果用条件判断代替取模要确保ik-n不会小于0。当ik n时ik-n的范围是0到n-1不会越界。但如果ik超过2n就会出问题。实际上i和j都小于nk小于n所以ik最大是2n-1ik-n最大是n-1安全。症状四结果不稳定。有时候对同一个字符串多次调用得到不同结果通常是因为字符串被修改了或者函数内部有静态变量没重置。最小表示法应该是纯函数不依赖任何外部状态。5.2 去重环节的隐蔽坑点去重看起来简单但有几个隐蔽的坑。第一个坑是字符串长度不同但最小表示串恰好相同。这种情况理论上不会发生因为循环同构不改变长度最小表示串长度等于原串长度。但如果代码里构造最小表示串时出错比如substr参数写错就可能产生长度不对的串。所以构造完最小表示串后最好检查一下长度是否等于原串长度。第二个坑是输入包含空行或空白字符。如果题目说字符串只含小写字母用cin s没问题。但如果输入格式不严谨可能读到空串。空串的最小表示没有意义需要在读入时过滤掉。第三个坑是setstring的比较开销。set默认用字典序比较对于长字符串每次比较可能扫描很多字符。如果N很大且字符串前缀重复度高set的性能会明显下降。这时候换成排序去重或者哈希去重更合适。第四个坑是内存限制。如果N10⁵每个字符串长度10³总长度10⁸存储所有最小表示串需要约100MB内存可能超过题目限制。这时候需要在线处理或者用哈希值代替完整字符串。5.3 性能优化实战技巧在实际使用中我总结了几个性能优化技巧按收益从高到低排列技巧一输入输出加速。加上ios::sync_with_stdio(false)和cin.tie(nullptr)对于大量输入输出能提升数倍速度。如果还嫌慢可以用scanf/printf或者手写快速读入。技巧二避免不必要的字符串拷贝。getMinString返回的是新构造的字符串如果只需要比较可以直接比较起始位置和原串避免构造新串。但这样比较逻辑会复杂一些需要权衡代码可读性和性能。技巧三按长度分组去重。如果字符串长度分布分散可以先用mapint, vectorstring按长度分组每组内部去重最后累加各组的不同串数量。这样能减少跨长度的无效比较。技巧四用哈希值代替字符串去重。对每个最小表示串计算一个64位哈希值用unordered_setunsigned long long去重。这样比较的是整数而不是字符串速度快很多。但要注意哈希冲突可以用双哈希或者大质数模数降低风险。技巧五提前终止比较。在最小表示法的比较循环中如果发现当前候选明显不可能成为最小表示可以提前跳出。不过标准算法已经足够高效这个优化收益有限。5.4 常见问题速查表下面用一个表格整理常见问题、原因和解决方法方便你快速排查问题现象可能原因解决方法结果比预期多最小表示计算错误不同类被当成不同检查跳跃逻辑和k重置结果比预期少去重过度不同类被当成相同检查最小表示串构造是否正确程序超时用了暴力法或去重效率低改用最小表示法排序去重程序崩溃空串或越界访问加空串检查用取模或条件判断内存超限存储了所有原始字符串在线处理只存最小表示串结果不稳定函数有副作用或静态变量确保函数纯函数化输入读不完输入格式理解错误检查是单组还是多组输入输出格式错误多组输出之间缺分隔按题目要求加换行或空格这个表格覆盖了我遇到过的绝大多数问题。每次调试时对照表格排查基本能快速定位原因。5.5 从这道题延伸出的实战经验这道题虽然是一道经典算法题但它背后的最小表示法在工程中用途很广。我举几个实际场景场景一循环日志去重。系统日志经常有周期性重复比如心跳日志每隔固定时间重复一次。把日志按周期切分后用最小表示法归一化就能快速统计不同模式的数量。场景二DNA序列分析。DNA是双链结构正链和反链、不同阅读框都可能产生循环同构。最小表示法可以用来归一化序列便于后续比对和聚类。场景三传感器信号处理。周期性信号在不同起始点采样会得到不同的序列但本质是同一个信号。用最小表示法归一化后可以准确识别重复信号。场景四文本查重。对于循环移位的文本抄袭比如把一篇文章的段落循环移位后重新组合最小表示法能帮助识别出这种变形。这些场景的共同点是数据具有循环结构需要找到唯一的代表元来去重或比对。最小表示法提供了一种高效、无冲突的解决方案。掌握它不仅能解决算法题还能在实际工程中派上用场。我在处理传感器数据时还遇到过一个变种问题字符串不是严格循环的而是允许一定程度的噪声。这种情况下最小表示法不能直接用需要先做去噪或者模糊匹配。但那是另一个话题了本文聚焦在精确循环同构的场景。最后分享一个调试小技巧当你怀疑最小表示法写错时可以写一个暴力版本作为对照。对小规模随机字符串分别用暴力法和最小表示法计算结果如果一致就说明算法正确。这个方法帮我定位过好几次隐蔽的bug。暴力版本虽然慢但逻辑简单不容易出错作为验证工具非常合适。
阅读完成 · 觉得有帮助？
