1. 问题引入从一道国赛真题看字符串处理的效率陷阱最近在复盘蓝桥杯的历年国赛真题2020年第十一届C组的“重复字符串”这道题给我留下了挺深的印象。它初看之下平平无奇甚至有点“送分题”的感觉不就是处理一个字符串让它变成某个重复子串的多次连接吗但真正动手实现尤其是想在竞赛的时限和内存限制下拿到满分你会发现里面藏着好几个关于C字符串操作、算法效率和边界处理的经典“坑”。很多同学止步于“暴力法能过样例”却不知道其算法在特定数据下会超时或者写出了逻辑正确但冗长脆弱的代码。这道题的核心场景是给定一个字符串S我们可以进行任意次操作每次操作可以修改S中的任意一个字符。目标是最终将S变为一个“重复字符串”。所谓“重复字符串”是指存在一个长度大于等于1的子串T使得S可以由T重复K次连接而成K是大于1的整数。题目要求我们找到最少的修改次数。举个例子字符串“abcab”。我们可以把它变成“abcabc”T“abc”,K2这需要修改最后一个字符‘b’为‘c’操作次数为1。也可以尝试变成“ababab”T“ab”,K3但这需要修改第3个字符‘c’为‘a’第5个字符‘b’为‘b’不变操作次数也是1。题目就是要求这个最小的操作数。乍一看我们需要枚举所有可能的重复单元长度len_T从1到S.length()然后检查每个长度下将原字符串对齐到这个重复模式需要修改多少次字符最后取最小值。思路很直接但魔鬼全在细节和效率里。直接无脑枚举和比对复杂度是O(n^2)当n达到10^5级别时必然超时。这就需要我们深入思考字符串的周期性特征并设计高效的统计方法。2. 核心思路拆解枚举周期与贪心统计解决这个问题的关键在于理解“重复字符串”等价于字符串具有周期性。如果最终字符串是T重复K次那么其长度n必须是len_T的整数倍。对于原字符串S我们假设其长度为n。我们只需要枚举所有可能的重复单元长度len其中len必须是n的约数。因为如果len不能整除n那么我们无论如何修改字符都无法让字符串长度n由长度为len的子串整数次重复构成。因此算法框架的第一步是找出字符串长度n的所有正约数。这些约数就是候选的重复单元长度len。对于每一个候选的len我们把字符串S想象成被切分成了k n / len个块每个块的长度都是len。我们的目标是修改S使得这k个块变得完全相同。那么最少的修改次数是多少呢这里就引出了第二个关键点列优先统计与多数表决。我们不能简单地逐个块去比较那样效率太低。一个高效的技巧是从“列”的角度来看。我们把这k个块上下堆叠起来形成一个有len列、k行的矩阵。第j列j从0到len-1就包含了所有块的第j个字符。例如S “aabbbc”,n6。假设我们枚举len2那么k3。三个块是“aa”,“bb”,“bc”。堆叠起来第0列a,b,b第1列a,b,c对于每一列我们的目标是让这一列的所有字符都变成同一个字符因为只有这样最终每个块在这一位置上的字符才相同。那么对于第j列最少需要修改多少次呢答案是将该列修改为出现次数最多的那个字符。假设该列有k个字符其中出现次数最多的字符出现了max_count次那么这一列最少需要修改的次数就是k - max_count把非主流的字符改成主流的。所以对于给定的len总的最少修改次数就是所有len列的这个值(k - max_count)的总和。我们遍历所有列累加这个值就得到了在这个重复单元长度下的最小操作数。最后对所有合法的len计算出的操作数取最小值就是全局答案。这个思路的精妙之处在于它将一个看似复杂的“让多个字符串相同”的问题分解为了len个独立的、简单的“让一组字符相同”的子问题并且每个子问题都可以用O(k)的时间通过哈希表统计字符频率来解决。整个算法的时间复杂度主要取决于1. 求所有约数2. 对每个约数len进行len次字符统计每次统计涉及k个字符。2.1 复杂度分析与可行性证明设字符串长度为n。首先求n的所有约数通常使用O(sqrt(n))的枚举方法即可。n的约数个数在10^5这个量级下不会太多通常少于200个这部分开销很小。对于每个约数len我们需要处理len列每列处理k n/len个字符。所以处理一个约数的代价是len * k n。也就是说处理每个约数的复杂度是O(n)那么总复杂度就是O(d * n)其中d是约数个数。在最坏情况下如果n是一个高度合数d可能会比较大但即便如此对于n 10^5d通常也在100量级100 * 10^5 10^7这个计算量在C中是完全可以在1秒内完成的蓝桥杯通常1s时限。这比最原始的O(n^2)枚举好了太多。这里有一个思维陷阱需要避免有人可能会想是不是只需要枚举len到n/2因为重复单元至少出现两次。是的K必须大于1所以len必须小于n。但我们的枚举是基于n的约数约数本身就排除了len n的情况因为K会等于1所以我们只需要枚举n的真约数大于0且小于n的约数即可。3. 手把手实现从算法到健壮代码理解了算法我们来看具体实现。我将代码分成几个函数使其逻辑清晰便于调试和讲解。3.1 第一步获取所有真约数vectorint getDivisors(int n) { vectorint divisors; // 只需遍历到 sqrt(n)注意完全平方数的情况 for (int i 1; i * i n; i) { if (n % i 0) { divisors.push_back(i); // i 是约数 if (i ! n / i i ! n) { // 避免重复和n本身 divisors.push_back(n / i); } } } // 注意我们需要的是真约数小于n的所以最后要过滤掉 n 本身如果被加进去了 // 实际上由于我们加了 i ! n 的判断n本身不会被加入。但为了安全可以再过滤一次。 vectorint properDivisors; for (int d : divisors) { if (d n) { properDivisors.push_back(d); } } return properDivisors; }注意这里有一个优化点。我们其实不关心约数的顺序但后续计算中len越小k就越大统计每列字符时循环层数可能外小内大。不过对总复杂度影响不大。确保不遗漏任何真约数即可。3.2 第二步计算给定长度len下的最小修改次数这是核心函数。输入字符串s和候选长度len返回使其成为重复字符串的最小操作数。int minChangesForLength(const string s, int len) { int n s.length(); int k n / len; // 重复次数 int total_changes 0; // 遍历每一列 for (int col 0; col len; col) { // 使用数组统计26个小写字母的出现次数题目通常给定字符集 // 如果字符集更大比如ASCII可以用大小为128的数组或者用unordered_map vectorint count(26, 0); int max_count_in_col 0; // 遍历该列的所有行即所有块 for (int block 0; block k; block) { // 计算当前字符在原字符串中的位置 int pos block * len col; char c s[pos]; int idx c - a; // 假设输入都是小写字母 count[idx]; // 实时更新当前列的最大出现次数 max_count_in_col max(max_count_in_col, count[idx]); } // 这一列需要修改的次数 总字符数 - 最大出现次数 total_changes (k - max_count_in_col); } return total_changes; }这段代码清晰体现了“列优先”统计的思想。两层循环外层遍历len列内层遍历该列的k个字符。使用一个固定大小的数组来统计频率比unordered_map更快前提是字符集已知且不大如26个小写字母。3.3 第三步主逻辑与边界处理现在我们把所有部分组合起来并考虑一些边界情况。#include iostream #include string #include vector #include algorithm #include climits // 用于INT_MAX using namespace std; // 上面两个函数 getDivisors 和 minChangesForLength 放在这里 int main() { string s; cin s; int n s.length(); // 边界情况1如果字符串长度小于2它本身不可能成为重复字符串K1 // 但题目可能保证n2不过为了健壮性可以判断。 if (n 2) { cout 0 endl; // 或者根据题意长度1无法操作输出0 // 实际上对于n1不存在长度小于n的真约数我们的算法会得到答案0。 return 0; } vectorint divisors getDivisors(n); int min_changes INT_MAX; bool found false; for (int len : divisors) { // len 已经是真约数即 1 len n int changes minChangesForLength(s, len); min_changes min(min_changes, changes); found true; } // 边界情况2如果字符串本身已经是一个重复字符串那么可能不需要任何修改。 // 我们的算法会枚举所有约数包括使得 changes0 的那个 len。 // 还有一种情况如果字符串所有字符都相同那么对于 len1 changes0。 // 所以 min_changes 最终会被更新为0。 // 边界情况3如果 divisors 为空理论上n是质数且大于1那么真约数只有1 // 那么循环不会执行min_changes保持INT_MAX。我们需要处理。 // 实际上对于质数n真约数只有1所以divisors不会为空。 // 但为了绝对安全 if (!found) { // 这种情况发生在 n1 时我们已经提前处理了。 // 如果 n 是质数divisors 会包含1。 min_changes n; // 一个保守的估计或者根据题意处理。 } cout min_changes endl; return 0; }3.4 一个完整的、优化过的示例代码将上述思路整合并加入一些细微优化比如在minChangesForLength函数中如果某列修改次数已经超过当前全局最小值可以提前剪枝我们得到最终版本#include bits/stdc.h using namespace std; int minChangesForLength(const string s, int len, int current_min) { int n s.size(); int k n / len; int total 0; for (int col 0; col len; col) { int cnt[26] {0}; // C风格数组更快 int max_cnt 0; for (int block 0; block k; block) { char c s[block * len col]; max_cnt max(max_cnt, cnt[c - a]); } total (k - max_cnt); // 剪枝如果当前累计修改数已经超过已知最小值后面就不用算了 if (total current_min) { return total; // 直接返回一个较大的值不影响min比较 } } return total; } int main() { string s; cin s; int n s.size(); int ans n; // 最坏情况每个字符都改也就是n // 枚举所有可能的重复单元长度 len (必须是 n 的约数且 len n) for (int len 1; len n; len) { if (n % len ! 0) continue; ans min(ans, minChangesForLength(s, len, ans)); } cout ans endl; return 0; }这个版本更简洁直接将枚举约数和计算整合在了一个循环里。ans初始化为n最坏情况然后枚举所有可能的len1到n-1检查是否为约数如果是则计算并更新答案。minChangesForLength函数中加入了剪枝优化当累计修改数已经超过当前最优解时提前退出计算节省时间。4. 深入讨论算法正确性证明与变种思考4.1 为什么贪心策略每列取众数是最优的这是一个需要想清楚的关键点。对于固定len分割后的k个块我们的目标是让它们完全相同。考虑最终相同的那个块它在第j列有一个确定的字符设为X_j。那么原字符串中所有在第j列位置上的字符最终都必须被修改为X_j如果原本不是X_j的话。因此对于第j列无论我们选择哪个字符作为最终的X_j需要修改的次数都是k减去该字符在列中原本出现的次数。为了使总修改次数最小我们自然希望每一列需要修改的次数尽可能少。那么对于单独一列显然选择出现次数最多的那个字符作为最终的X_j能使k - max_count最小。并且各列之间的选择是独立的。第j列选择字符A作为最终字符并不会影响第j1列选择字符B。因此分别对每一列采取贪心策略选择众数组合起来就是全局最优解。不存在一种方案通过让某一列不选择众数来使得其他列节省更多的修改次数因为列与列之间没有耦合关系。4.2 处理大写字母或其他字符集题目通常说明字符串仅由小写字母构成所以我们用了cnt[26]。如果字符集扩大比如包含大小写字母和数字有几种方法使用unordered_mapchar, int通用但常数时间开销比数组大。使用更大的数组如果确认是ASCII字符可以int cnt[128] {0};然后直接用字符作为下标cnt[c]。使用vectorint(256, 0)类似数组。在竞赛中如果未明确说明优先假设为小写字母。若存疑使用unordered_map是最稳妥的除非性能成为瓶颈。4.3 如果允许的“操作”定义不同怎么办原题是“修改任意字符”。如果操作变成“交换任意两个字符”或者“插入/删除字符”问题就完全不同了。交换字符这变成了一个排列问题可能需要计算字符串的循环节或者通过统计字符频率来匹配。目标是让字符串具有周期性且不改变字符的多重集合。插入/删除字符这变成了编辑距离问题的一个变种或者需要动态规划来匹配一个重复模式。复杂度会显著上升。所以审题时明确“操作”的定义至关重要。本题的“修改”操作是最简单的一种它只改变字符本身不改变字符串长度和字符的相对位置从而允许我们进行独立的列统计。4.4 性能实测与复杂度再验证为了确保我们的O(d * n)算法在n10^5时确实可行我们可以进行一个思想实验。n的最大约数个数d(n)在10^5附近是多少一个极端例子是n83160它有超过100个约数。即使d128,128 * 100000 12,800,000也就是一千两百万次操作。在C中一次内层循环操作数组索引、自增、比较通常只需要几个时钟周期。现代CPU每秒能执行数十亿次操作所以一千两百万次循环完全可以在几十毫秒内完成远低于1秒时限。在实际编码时使用C风格数组int cnt[26] {0};比vectorint(26,0)稍快因为它在栈上分配没有构造函数开销。在minChangesForLength函数中对于每一列我们都重新初始化这个数组由于长度固定为26使用memset或直接循环赋零也可以但int cnt[26] {0};的写法在循环中每次都会重新初始化是清晰且高效的。5. 常见错误与调试技巧即使思路正确实现时也可能踩坑。下面列举几个我调试时遇到过或者常见的问题5.1 下标计算错误这是最容易出错的地方。计算原字符串中对应第block块、第col列的字符位置时公式是int pos block * len col;一定要确保block从0开始到k-1结束col从0开始到len-1结束。可以写一个简单的测试用例验证比如sabcdef,len2,k3。那么block0, col0 - pos0 - ‘a’block0, col1 - pos1 - ‘b’block1, col0 - pos2 - ‘c’block1, col1 - pos3 - ‘d’block2, col0 - pos4 - ‘e’block2, col1 - pos5 - ‘f’ 这符合我们将“abcdef”分成“ab”,“cd”,“ef”三个块的直觉。5.2 忽略字符集假设如果题目没说只有小写字母而你用了c-‘a’作为下标遇到大写字母或数字就会数组越界导致运行时错误如段错误。在不确定时要么先确认题意要么使用unordered_map。蓝桥杯题目描述通常比较严谨会说明“由小写字母组成”。5.3 未处理len n的情况在我们的算法中len必须小于n因为K要大于1。如果你在枚举约数时不小心包含了n本身那么k n / n 1。此时对于任何一列max_count总是1因为只有1个字符k - max_count 0。这会导致计算结果为0即“不修改任何字符”但这不符合“重复字符串”的定义K1不算重复。所以必须排除len n的情况。我们的getDivisors函数通过if (i ! n)的判断排除了它在主循环中枚举len从1到n-1也自然排除了。5.4 初始化与重置频率数组在minChangesForLength函数中对于每一列频率数组必须清零。如果使用vectorint count(26, 0)它在每次循环开始时都会重新构造并初始化为0是正确的。如果使用int count[26];然后试图用memset(count, 0, sizeof(count));来清零要确保sizeof(count)计算正确。更推荐在循环内直接定义int cnt[26] {0};写法简洁且不易错。5.5 答案初始值最小修改次数的初始值应该设为一个较大的数比如n最多每个字符都改一次。不能初始化为0否则min操作永远会得到0。5.6 测试用例设计自己设计几个测试用例来验证程序简单情况s”aaaa”, 答案应为0本身已是重复字符串T”a”,K4。需要修改s”abcab”, 答案应为1如开头所述。所有字符都不同s”abcdef”(n6)。枚举约数1,2,3。len1: 需要把5个字符改成和第一个字符‘a’一样不对对于len1每列只有一个字符max_count1总修改数0这里要小心len1意味着T是单个字符Kn。我们的算法k6只有1列。这一列有6个字符{a,b,c,d,e,f}出现次数最多的字符出现了1次所以修改次数6-15。这是合理的因为要变成“aaaaaa”需要改5个字符。len2: k3。列0:{a,c,e}众数出现1次修改2次列1:{b,d,f}众数出现1次修改2次总计4次。len3: k2。列0:{a,d}修改1次列1:{b,e}修改1次列2:{c,f}修改1次总计3次。最小值为3。所以答案是3。可以验证比如变成“abcabc”(T”abc”, K2) 需要改3个字符d-a, e-b, f-c。边界情况s”a”(n1)。根据题目定义长度1无法构成K1的重复字符串。我们的算法中len从1到0循环不会执行ans保持初始值n1。但也许题目期望输出0需要仔细读题。通常对于无法操作的情况输出0是合理的因为无需修改就已经… 但严格说不满足条件。蓝桥杯真题通常保证n 2所以这个边界可能不会出现。为了健壮性可以在开头判断if(n2) {cout0; return 0;}。6. 从这道题延伸的算法与字符串技巧这道“重复字符串”题虽然归类为字符串问题但它核心考察的是枚举、约数、贪心以及问题转化的能力。它把字符串周期性问题转化为了列统计问题这是一个非常漂亮的思路。与此相关的经典算法和技巧有KMP算法与字符串周期KMP算法中的next数组可以用来判断一个字符串的最小循环节。如果一个长度为n的字符串S有长度为len的最小循环节那么n % len 0且len n - next[n]如果next[n] 0。对于本题我们可以利用这一点快速找到所有可能的周期长度吗可以但需要注意KMP找到的是最小循环节。如果一个字符串有周期len那么len一定是最小循环节长度的倍数。所以我们可以先求出最小循环节长度min_len然后枚举min_len的所有倍数同时是n的约数作为候选len。这可以稍微减少枚举量但实现KMP本身也有开销对于本题的数据范围直接枚举所有约数已经足够高效。前缀和与字符统计如果题目不是修改字符而是询问“子串中某个字符出现的次数”那么前缀和技巧就派上用场了。我们可以预处理一个二维前缀和数组pre[i][c]表示前i个字符中字符c出现的次数。这样可以在O(1)时间内回答任何区间[l, r]内字符c的出现次数。虽然本题用不上但这是处理字符串区间统计问题的利器。哈希与字符串快速比较如果题目要求判断两个子串是否相等或者判断字符串是否有周期性字符串哈希如Rabin-Karp哈希可以在O(1)时间内完成比较预处理O(n)。例如我们可以计算字符串S的哈希值然后判断S是否等于T重复K次可以通过比较S的哈希值与T的哈希值经过特定计算后的值是否相等来判断。这在一些更复杂的字符串周期性问题中很有用。回到这道蓝桥杯真题它更像是一个思维体操训练我们将复杂问题分解、转化并利用基础数据结构数组高效统计的能力。在竞赛中遇到字符串问题先别急着上复杂的自动机或后缀结构想想能不能通过枚举、贪心、前缀和等简单方法解决。往往最优雅的解法就藏在最基础的思考之中。