1. 题目到底在说什么CF1029A 的题面与直觉理解1.1 题面一句话版本与样例CF1029A 的题面很短短到第一次读的时候很容易觉得自己已经懂了然后代码一写就错。题目是给你一个字符串t和一个整数k要你构造一个最短的字符串s使得t在s中恰好出现k次。注意这里的“出现”是允许重叠的。这意味着如果t aba那么s ababa里就出现了两次aba——一次从下标 0 开始一次从下标 2 开始两个匹配串在中间的a上撞在一起。这是解题的题眼也是几乎所有新手第一次提交 WA 的根源。题目给的例子可以辅助理解t aba, k 2时答案是ababa长度 5 而不是 6。如果不允许重叠答案自然会写成abaaba但那样就不是最短了。t ab, k 2时答案显然是abab因为没有任何重叠空间老老实实把 ab 接两遍。t a, k 5时答案就是aaaaa每个字符都能作为新一次匹配的起点。这道题的核心就是在问两个相同的字符串首尾相连时最多能共用多少个字符这个“最多能共用的字符数”有一个专门的名字叫最长相等真前后缀英文社区一般叫 longest border 或 longest proper prefix-suffix。1.2 大多数人第一反应为什么会错我第一次做这道题的时候思路是“把t重复 k 次不就行了”。当k2时这就是t t但t t不一定最短。问题出在哪看t ababatt ababaababa但ababaababa里从头到尾数一下ababa出现的位置有 0、2、5、7一共四次——超过了题目要求的两次。也就是说直接重复会把不必要的匹配次数带出来同时也意味着我们确实可以把某些部分的字符重叠掉让总长度更短。这里有一个矛盾点我们要的是“恰好 k 次”而不是“至少 k 次”。恰好意味着既不能多也不能少。当你把t接在t后面时一旦两个t之间有重叠就会自然形成一个公共的“接缝区”这个区域里新串和旧串共享一堆字符。如果你重叠的不是最长的那一块可能导致匹配次数多于预期如果你重叠的过长又可能让字符不够用。正确做法不是简单拼接而是要找出t的最长相等真前后缀把前一个t的“尾巴”和后一个t的“头”重叠起来然后反复使用这个重叠关系构造s。1.3 重叠是题眼出现次数允许“串在一起”在字符串算法里“重叠匹配”是一个高频考点。KMP 为什么难理解因为 KMP 的核心是 fail 指针fail 指针的本质就是在失配时退回到上一个可能的“重叠位置”。Z 函数算出的Z[i]本质也是在描述每个后缀和整个字符串能重叠多长。CF1029A 虽然数据范围小到 50完全可以暴力但它的模型和 KMP 是同一个。换句话说你把这题做透KMP 的直觉你也就有了大半两个相同字符串放在一起能省多少字符取决于它们的最长共同前后缀有多长。所以整篇文章的主线就是三件事什么是“最长相等真前后缀”怎么用它构造最短目标串为什么这样构造出来的串一定是“恰好 k 次”且“最短”。下面逐步展开。2. 核心工具最长相等真前后缀border的完整拆解2.1 什么是真前后缀为什么“真”字那么重要一个字符串的前缀是从开头开始的任意子串后缀是从结尾结束的任意子串。“真前缀”和“真后缀”意味着这个子串不能等于整个字符串本身。比如t ababa真前缀a,ab,aba,abab真后缀a,ba,aba,baba在这些前缀里有一些同时也是一个后缀这些就是“相等的前后缀”。对ababa来说a是前缀也是后缀长度为 1aba是前缀也是后缀长度为 3长度 5 的ababa确实也是前缀和后缀但它是整个串本身被“真”字排除。所以最长相等真前后缀是aba长度 3。这个数记为border_len。为什么要把“整个串本身”排除掉因为在字符串重叠拼接的场景里如果你把整个t自己当成前后缀来重叠那就意味着两边完全重合等于没有新增字符构造过程就卡死了。我们的直觉是两份t拼在一起重叠的部分必须小于len(t)这样第二份t才能往右延伸出新的字符。这里可以用生活化的类比两个人排队第二个人站得太靠前整个人都被第一个人挡住了等于队伍没变长他必须露出至少一个身位队伍长度才会增加。这个“露出的身位”就是len(t) - border_len。2.2 最长公共部分决定了拼接时的可复用长度假设我们把两份t首尾拼接让第一份的后缀和第二份的前缀尽可能地重合重合的长度就是border_len。拼接后的串结构是t本身 t从 border_len 到末尾的部分举个例子t abababorder_len 3。拼接时两份t共享aba这三个字符得到t: a b a b a 拼接后的 s: a b a | b a a b a b a 最终: a b a b a b a也就是s abababa。注意s里ababa出现了三次位置 0、位置 2、位置 4。这正好对应k 3的情况。为什么只能用最长 border而不能随便找一个更短的因为短 border 能重叠的字符少拼接出来的总长度更长。我们的目标是“最短”所以要取能重叠的极限也就是最长的那一个。再举一个更直观的例子t abcab它的最长相等真前后缀是ab长度为 2。两份t拼在一起中间共享ab结果是abcabcab。我们来拆开看第一份: a b c a b 第二份: a b c a b 结果: a b c a b c a b这里abcab在结果中的出现位置是 0 和 3恰好两次。如果把第二份完全不重叠地接在后面结果是abcababcab长度从 7 膨胀成 10显然不是最优。2.3 暴力求 border 的写法与复杂度CF1029A 的约束是n ≤ 50k ≤ 50小到可以完全忽略效率问题所以暴力求 border 完全够用。求法很直接从n - 1往下枚举可能的 border 长度L第一个满足t.substr(0, L) t.substr(n - L, L)的L就是答案。#include bits/stdc.h using namespace std; int main() { int n, k; string t; cin n k; cin t; int border_len 0; for (int L n - 1; L 1; --L) { if (t.substr(0, L) t.substr(n - L, L)) { border_len L; break; } } string s t; string tail t.substr(border_len); for (int i 1; i k; i) { s tail; } cout s \n; return 0; }这里border_len初始为 0表示没有任何相等真前后缀。如果t abc前缀和后缀没有相同的除了整个串自己t.substr(0, 2) abt.substr(1, 2) bc不相等L 1时a和c也不相等所以border_len 0。最终构造结果就是abc重复 k 遍。tail t.substr(border_len)的含义是每追加一次tail就相当于让新的一份t利用前面已经存在的后缀只补上自身没有重叠的那部分。这样做 k-1 次就得到恰好 k 次匹配的最短串。3. 构造策略的数学推导为什么答案是 t 加 k-1 次尾巴3.1 贪心思路每次尽可能少补新字符现在把问题抽象成一步已经有了一个字符串s它的后缀正好是t的某个前缀我们在s后面追加一些字符让t在s尾部再完整出现一次。假设s的后缀能匹配t的前缀长度为L也就是尾部已经有t[0..L-1]这些字符。那么为了在尾部形成一个完整的t还需要补上t[L..n-1]这一段一共n - L个字符。为了让总长度最小我们要让这个“已经匹配的前缀长度”L尽量大。而s尾部在构造过程中始终是某个t的后缀接上若干t的片段它能够与t前缀匹配的最大长度恰好就是整个字符串t的“最长相等真前后缀”。为什么因为构造步骤中s以一份完整的t开头之后每一次追加的都是t的一个尾巴从border_len之后才开始。考察任意相邻两份t的衔接处真正决定重叠量的就是t自身前缀和后缀的关系。这是一个只与t自身性质有关的问题和前面已经拼了多少份无关。3.2 用 border 做重叠的几何演示画一个直观的三份重叠图。设border_len B每份t长度为n。第一份 t: [ n ] 第二份 t: [ 从 B 开始 ] 拼接后: [ n | n-B ] 第三份 t: [ 从 B 开始 ] 最终: [ n | n-B | n-B ]所以最终结果的长度就是len(s) n (k - 1) * (n - B)对照前面的例子t ababan 5B 3k 3时len(s) 5 2 * 2 9确实就是ababababa的长度。检查一下匹配次数第一份t自身的出现是第 1 次之后每追加一个n - B长度就会在新增的尾巴里形成一次新的完整匹配。追加k - 1次总匹配次数就是k次。这是从构造方式里直接推出来的不需要额外的字符串计数。3.3 最短性论证为什么不能更短这个题最容易忽略的部分是证明“最短”。代码好写但如果你在题解评论区看到有人问“为什么不能每次只加一个字符然后把 t 凑出来”你就知道很多人其实没想透。反证法考虑任意一个满足条件的字符串s它的长度记为m。s里共有k次t出现其中第一次出现从位置 0 开始的情况我们不做假设但至少存在一次出现。对于任意两次出现它们的起始位置差d必须满足d ≥ 1并且当第二次出现开始时前一次出现还没结束的部分就是重叠部分。这个重叠部分长度必须在 0 到n-1之间。考察所有可能的d最紧凑的排布方式是把每相邻两次出现都重叠到极限。既然重叠部分只能是一个既是t前缀又是t后缀的公共部分那么最大重叠长度就是B。也就是说任意相邻两次出现之间的起始位置差最小也只能是n - B。因此k次出现之间总偏移至少是(k - 1) * (n - B)再加上第一份t本身的长度nm ≥ n (k - 1) * (n - B)。而我们构造出来的串长度正好等于这个下界所以它一定是最短。这个结论告诉我们一件事不要试图在构造过程中“跨越多份 t”设计更复杂的重叠方案因为任何重叠都是两两相邻的而两两之间能达到的最大重叠已经被 B 界定死了。3.4 最终公式与长度计算整理一下最终构造规则s t (t.substr(B)) 重复 (k - 1) 次如果B 0s t重复 k 次这其实就是平凡情况如果B n - 1比如t aaaas就是a重复(n (k-1)*1)次每次追加 1 个字符就产生一次新匹配。用一个例子验证t aaaa, k 3B 3 tail t.substr(3) a s aaaa a a aaaaaaaaaa在aaaaaa中出现几次位置 0、1、2共 3 次长度 6完全符合公式4 2 * 1 6。再看一个容易算错的t ab, k 3。B 0 s ab ab ab abababab出现 3 次长度 6等于2 2 * 2。这个例子说明没有重叠时每次都得补完整的一份。4. 代码实现与提交C 写法、边界条件、常见坑4.1 一份可以直接 AC 的完整代码下面这份代码按照 CF 的标准输入输出写好了提交即用。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; string t; cin n k t; // 求最长相等真前后缀长度 border_len int border_len 0; for (int len n - 1; len 1; --len) { bool ok true; for (int i 0; i len; i) { if (t[i] ! t[n - len i]) { ok false; break; } } if (ok) { border_len len; break; } } // 构造答案 string ans t; string tail t.substr(border_len); for (int i 1; i k; i) { ans tail; } cout ans \n; return 0; }注意这里我用了双重循环判断前后缀相等没有直接调substr比较。原因不是substr不行而是为了让你看清它在干嘛——t[0..len-1]和t[n-len..n-1]是不是完全一致。理解这一点比调库更重要以后遇到n 1e6的场景你必须知道这是在枚举所有可能的 border 候选才能想到用 KMP 的 fail 数组一次性求完。4.2 边界条件逐条检查写完后提交前至少要自己过这几组测试n 1时t a循环从len 0开始就不进入border_len 0tail a结果就是k个a。因为单字符串没有真前后缀可言每次补一个字符就出来一次匹配正确。k 1时ans t循环一次都不执行正确。这时候甚至不需要求 border但算一下也无妨。t全由相同字符组成如zzzzborder_len 3tail z输出长度4 (k - 1)。你可以手动验证zzzz在结果串里出现的位置是连续的每 1 个字符一次次数吻合。t完全没有任何相同前后缀如abcborder_len 0输出就是abcabcabc...每 3 个字符出现一次次数吻合。还需要注意k的上限是 50n的上限也是 50最坏情况下答案长度是50 49 * 50 2500远小于任何字符串库的极限。这个题的数据范围刻意开得很小所以基本不会出现性能问题。4.3 如果 n 和 k 放大到 1e5你的暴力法就死了如果你只是想做掉这道 CF 题上面的代码已经足够了。但如果你回头看代码里那两重循环会发现求 border 是O(n^2)的构造是O(k * n)的在n, k ≤ 50时无所谓一旦数据范围放大这套代码立刻超时。这里先不展开 KMP 的细节到第 6 节我们再聊优化方案。我想强调的是暴力求 border 的思路和 KMP 求 fail 数组的思路完全一致只是后者用动态规划的思想把复杂度压到了 O(n)。做这种小范围题时养成“求 border 就想到 KMP 的 fail 指针”的习惯后面做 harder 版本会很省力。5. 复盘踩过的坑与调试思路5.1 坑一把“恰好”理解成“至少”导致构造过长有些人做这题时构造方法可能是先拼出一个s然后用字符串匹配算法数一遍t出现了几次如果多了就删字符少了就加字符。这个思路在小数据下也能跑但它绕了一个大弯而且很容易在“删字符”这一步走进死胡同。比如t aa, k 1直接输出aa就行。但如果你按“先拼 k 份再缩减”的思路拼出aaaa后数出 3 次匹配想删字符缩减到恰好 1 次无论怎么样都会失败因为aa是没法再压缩的。我见过的错误提交里不少是输出了aa重复 k 次也就是忽略了重叠。这类错误本质上不是代码问题而是没有意识到“恰好”和“重叠”这两个限定词同时出现时的含义。5.2 坑二求 border 时循环边界写错这是最常见的边界 bug。枚举len时从n - 1开始往下递减到1结束。如果把len n也算进去那么t[0..n-1]和t[0..n-1]必然相等border_len会变成n导致tail t.substr(n)为空字符串构造出来的s就只有一份t永远不可能出现 k 次。这是我第一次写时踩到的坑排查了半天才意识到是 border 长度把整个串自己算进去了。另一种错误是后缀起点写错。判断前后缀相等后缀的起点应该是n - len不是len也不是n - len 1。写错一格会导致abcde这种正常串被误判出 border。建议调试时打印一下每一步的len、t[0..len-1]、t[n-len..n-1]一目了然。5.3 坑三构造串时用t tail而不是ans tail有人会写出这样的代码string ans t; for (int i 1; i k; i) { ans t.substr(border_len); // 这里每次追加的 tail 是一样的 }这个写法本身没错。但如果写成ans t;那就完全忽略了 border构造出来的串虽然也能凑出 k 次匹配但长度不是最短。CF 对这类题有 special judge 或者对长度有严格限制提交时不一定报 WA但如果你做过t aba, k 2这个样例就能立刻看出问题错误答案abaaba和正确答案ababa一个 6 一个 5哪个短一眼便知。还有一个小问题k次循环如果从 1 开始那么答案已经有了一份 t循环只需要执行k - 1次如果从 0 开始就要小心多拼一份。这种 off-by-one 错误在k 1的时候最容易暴露。5.4 我的调试过程从 WA 到 AC 的完整链路说完坑还原一下我自己做题时从 WA 到 AC 的完整排查过程方便你以后遇到类似问题有个参考。第一次提交的代码长这样string ans t; for (int i 0; i k; i) ans t; cout ans;这甚至没算 border直接拼了 k1 份样例居然过了t ab, k 2因为ab ab ab ababab里ab出现 3 次而不是 2 次所以这个代码连样例都不全对。正确的后方一致。后来改成了string ans; for (int i 0; i k; i) ans t;这输出了 k 份 t 的拼接。t ab, k 2答案是abab这个代码能过t aba, k 2输出abaaba而正确答案是ababaWA。然后我开始画图发现两份aba之间最多能重叠 1 个字符最长的真前后缀是a于是修改为int border_len 1; // 我就知道这一个串有 border其他情况呢这个代码过了样例但t abc, k 3就挂了因为abc没有 border。最终我老老实实写了个循环把所有t都算了 border终于 AC。回过头看这个一步步发现问题、补全逻辑的过程其实就是从“凭直觉拼串”进化到“抽象出前后缀模型”的过程。如果你现在还在 WA不妨也按这个顺序自查一下先确认你有没有在算 border再确认 border 是否把整串算进去了最后确认循环次数对不对。6. 思维拓展从 CF1029A 到 KMP、哈希与多题通用套路6.1 如果 n 和 k 放大到 1e6 怎么办CF1029A 的原题数据很小但很多变体题会把k放大到10^9。这时候显然不能真的把字符串拼接出来但题目只问你最短长度于是公式就派上用场了最短长度 n (k - 1) * (n - border_len)你依然需要求出border_len但求法不能是暴力O(n^2)。标准解法是用 KMP 的前缀函数prefix functionvectorint prefix_function(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; } return pi; }pi[n-1]就是整个字符串t的最长相等真前后缀长度即border_len。复杂度O(n)空间O(n)。如果你问为什么pi[i]能一路跳回去找到最长 border可以这样理解pi[i]记录的是s[0..i]的最长 border 长度。如果下一个字符失配你不能退到i之前的任意位置只能退到当前最长 border 长度的位置因为更长的前缀已经不可能匹配了。这个“跳转”过程保证每个字符最多被比较 O(n) 次所以总体线性。6.2 字符串重叠问题的通用模型把这类题抽象一下就是下面这个模型已知一个模式串 P 重复拼接允许相邻两份共享前缀后缀问第 k 次完整出现时整个文本的最短长度。这个模型的三个要素重叠的长度上限由border决定也就是P的前缀集合与后缀集合的交集的最大值每次新增的步长len(P) - border_len相当于每次“前进”的字符数总长度公式len(P) (k-1) * 步长。很多字符串题本质上都在算这三样东西。比如 LeetCode 上有一类题给你一个字符串问重复多少次才能包含另一个串还有一类题问两个字符串拼接成回文串的最短长度也和前缀后缀匹配有关。你只要抓住“寻找最长公共前后缀”这个核心这些题就都能拆成同一个套路。6.3 一题多解Z 函数、字符串哈希与暴力除了 KMP 前缀函数还有两种常见办法求border_lenZ 函数计算出Z[i]表示从 i 开始的后缀和整个字符串的最长公共前缀长度。border_len就是所有满足i Z[i] n的i中Z[i]的最大值。它的思想是“从后缀位置反推”和前缀函数从前往后推正好相反。字符串哈希预处理前缀哈希二分枚举长度或从大到小枚举长度判断hash(0, L-1) hash(n-L, n-1)。在需要处理多模式串或配合二分答案的场景下哈希的灵活度更高。三种方法在n不大的情况下都能 AC但 KMP 的前缀函数是最贴近题目本质的因为你只需要一次线性扫描而且不会遇到哈希碰撞的玄学问题。6.4 相关题目与训练建议如果你喜欢用“一题多解”的方式刷题建议在 CF1029A 之外做以下这些题作巩固Codeforces 432D Prefixes and Suffixes直接考察前缀函数要求统计每个前缀在串中出现的次数和本题的 border 概念一脉相承Codeforces 126B Password要求找一个同时是前缀、后缀、并且还在中间出现过的子串是对 border 概念的进一步深挖LeetCode 459 Repeated Substring Pattern判断字符串是否能由其某个子串重复构成本质上是考察border与周期的关系。做这些题时可以把今天推导出的两个结论作为通用武器一个字符串的最长 border 长度决定了它“自我重叠”的最大能力如果有多个重复模式串需要拼接最短拼接长度永远是n (k-1) * (n - border_len)。最后再分享一个我实际调题时的小技巧如果你不确定自己算出的border_len对不对写一个while循环暴力在构造出的s上数一遍t的出现次数把这个次数打印出来和k比对。数据只有 50暴力数绝对来得及。等你确认自己的构造串确实“恰好 k 次”了再把它提交上去。这个方法能筛掉九成以上的边界 bug尤其是在你刚接触字符串题、脑子还停留在“字符串匹配必须一次滑一格”的阶段时暴力验证是帮助你建立直觉的最快路径。