1. 问题引入从“重复字符串”到“周期模式”的思维跃迁在算法竞赛和日常开发中字符串处理都是基本功。蓝桥杯国赛级别的题目往往不会直接问你“如何判断一个字符串是否由某个子串重复构成”这么简单。它会把问题包装在一个更复杂的场景下考察你能否透过现象看本质将实际问题抽象为经典的字符串周期性问题。这道“重复字符串”的真题就是一个绝佳的例子。乍一看标题你可能会想到暴力枚举所有子串但国赛的题目数据规模和时间限制注定会让暴力解法超时。这道题的核心其实是要求你高效地找到一个字符串的“最小重复单元”或者说判断它是否是一个“周期串”。我见过很多同学一遇到字符串问题就下意识地开始写双指针循环结果代码又长又容易出错还通不过大数据测试。实际上对于这类寻找重复模式的问题有一个非常经典且高效的算法——KMP算法中的next数组或者称为部分匹配表可以让我们在O(n)的时间复杂度内解决它。今天我就结合这道蓝桥杯国赛真题带你彻底搞懂如何利用KMP的思想来优雅地解决“重复字符串”及其变种问题。我们不止步于AC这道题更要掌握其背后的“周期定理”和算法思维让你下次遇到类似问题能一眼看穿本质。2. 题目场景还原与核心诉求分析虽然我们手头没有原题的全部描述但根据“重复字符串”这个标题结合蓝桥杯常见的出题风格我们可以合理地还原出题目的典型场景和需求。这类题目通常不会直接给你一个字符串让你判断而是会嵌入一个更具体的上下文。2.1 典型的题目叙述方式题目可能会这样描述给定一个字符串S其长度为N。我们可以进行一种操作选择S的一个前缀即从开头开始的连续一段然后将其重复若干次至少一次来尝试构造出整个字符串S。问是否存在这样的一个前缀使得通过重复它可以得到原字符串S。如果存在输出这个最短前缀的长度如果不存在输出-1或者特定的标识。例如对于字符串abcabcabc前缀abc重复3次即可得到原串因此答案是3。对于字符串ababab前缀ab重复3次即可得到原串因此答案是2。对于字符串abcde没有任何一个前缀重复整数次后能等于它自身除了整个字符串重复1次但这通常不符合“重复”的题意或者题目要求重复次数大于1因此答案是-1或N视题目具体要求而定。2.2 问题的数学化与抽象我们把上述问题抽象一下对于一个长度为n的字符串s我们想要求一个最小的正整数len使得len能整除n。对于所有0 i n都有s[i] s[i % len]。换句话说字符串s是以s[0:len]这个子串为周期不断重复构成的。len就是这个字符串的“最小周期”。如果len n则意味着字符串没有比自身更小的周期即它不是由一个更短的前缀重复构成的。2.3 输入输出与数据规模考量蓝桥杯国赛级别的题目数据规模N通常会在10^5甚至10^6级别。这意味着O(n²)的暴力算法枚举所有可能的前缀长度len然后检查s是否由其重复构成是绝对行不通的。我们必须设计一个O(n)或O(n log n)的算法。这直接引导我们向KMP算法的next数组寻求解决方案因为它能在O(n)的预处理后以O(1)的代价回答关于字符串周期的查询。3. KMP的next数组不只是字符串匹配的工具很多同学学习KMP算法只记住了它用来做字符串匹配却忽略了其核心副产品——next数组——所蕴含的关于字符串自身结构的深刻信息。理解这部分是解决本题的关键。3.1 next数组的定义与计算对于一个长度为n的字符串s下标从0开始我们定义next[i]0 i n为子串s[0...i]的最长相等真前缀与真后缀的长度。“真前缀”指不等于自身的前缀。“真后缀”指不等于自身的后缀。“最长相等”指找到的那个前缀和后缀必须完全一样。例如字符串ababcab对于i4子串ababc其真前缀有a,ab,aba,abab真后缀有c,bc,abc,babc。其中没有相等的所以next[4] 0。对于i6子串ababcab其真前缀有a,ab,aba,abab,ababc,ababca真后缀有b,ab,cab,bcab,abcab,babcab。相等的有a和a长度1ab和ab长度2。最长的长度为2所以next[6] 2。计算next数组有一个经典的O(n)算法其核心思想是“前缀指针”的回退这里简要回顾一下代码因为它是我们后续所有推导的基础public static int[] getNext(String s) { int n s.length(); int[] next new int[n]; next[0] -1; // 通常习惯将next[0]设为-1方便编程也有设为0的变体。本文采用-1的版本。 int i 0, j -1; while (i n - 1) { if (j -1 || s.charAt(i) s.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; }这个算法中i是当前待计算next[i]的位置j指向前缀的末尾。理解这个双指针的跳动过程是理解KMP的关键。3.2 next数组揭示的周期性质这是最核心的部分。对于一个字符串s计算完next数组后考虑最后一个值next[n-1]假设下标从0开始字符串长度为n。它代表了整个字符串s的最长相等真前缀/后缀的长度。现在我们定义len n - next[n-1]。如果n % len 0那么len就是字符串s的最小周期长度而n / len就是它重复的次数。为什么next[n-1]表示字符串有一个长度为L next[n-1]的真前缀同时也是一个真后缀。这意味着字符串的后L个字符和前L个字符是一样的。去掉这个共同的后缀也是前缀剩下的部分长度为n - L。整个字符串的结构可以看作是[前缀A][后缀B]其中后缀B 前缀A的一部分不更准确地说因为后缀等于前缀所以字符串实际上是[X][Y]其中[Y]等于某个前缀。通过数学归纳和字符串的自我比较可以推导出如果n % (n - L) 0那么字符串就是由前n-L个字符重复构成的。一个具体的例子s abcabcabc,n 9。 计算next数组过程略得到next[8] 6。abcabca的最长相等前后缀是abca我们来仔细算真前缀abcabca... 实际上对于abcabcabc手工计算next较复杂但结论是next[8] 6因为abcabc既是前缀也是后缀。 那么len n - next[8] 9 - 6 3。n % len 9 % 3 0。 所以最小周期len 3即abc重复次数为9 / 3 3。另一个例子s ababa,n 5。next数组next[4] 3abab的最长相等前后缀是ab长度2这里需要仔细计算子串ababa的真前缀有a,ab,aba,abab真后缀有a,ba,aba,baba。相等的有a(1)和aba(3)。最长是aba长度3。所以next[4]3。len 5 - 3 2。n % len 5 % 2 1 ! 0。 所以虽然len2即ab看起来像是个周期但5不能被2整除因此整个字符串ababa并不是由ab简单重复构成的ab重复2次是abab重复3次是ababab都不等于ababa。它不是一个严格的周期串。next数组的性质告诉我们它具备一定的“循环节”特征但不是完整的整数倍循环。4. 算法实现与代码逐行解析理解了原理我们来看如何用Java实现。我们的目标是读入一个字符串判断它是否由某个前缀重复多次构成如果是输出那个最短前缀的长度否则输出-1或根据题目要求输出其他值。4.1 基于next数组的解决方案import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s scanner.next(); int n s.length(); // 1. 计算next数组 (这里使用next[0]-1的版本) int[] next new int[n 1]; // 多分配一位方便处理让next[i]表示s[0...i-1]的next值 next[0] -1; int i 0, j -1; while (i n) { if (j -1 || s.charAt(i) s.charAt(j)) { i; j; next[i] j; // next[i] 现在对应的是s[0...i-1]的信息 } else { j next[j]; } } // 2. 核心判断利用next[n] 即整个字符串s[0...n-1]的next值 // next[n] 表示整个字符串的最长相等真前后缀长度 int longestCommonLen next[n]; // 注意这里用的是next[n]不是next[n-1] // 可能的最小周期长度 int candidateLen n - longestCommonLen; // 3. 判断是否满足周期条件 if (candidateLen 0 n % candidateLen 0) { // 是由前缀重复构成 System.out.println(candidateLen); } else { // 不是由前缀重复构成 System.out.println(-1); // 或者输出 n根据题目要求调整 } scanner.close(); } }4.2 代码关键点剖析与避坑指南next数组的长度与含义这里我使用了长度为n1的数组并让next[i]表示子串s[0...i-1]的信息。这样做的目的是让next[n]直接表示整个字符串s的信息代码更清晰。如果你习惯用长度为n的数组那么需要关注next[n-1]并在计算candidateLen时使用n - next[n-1]。两种方式本质等价但下标容易出错选定一种并保持一致。candidateLen 0的判断这个条件至关重要。考虑字符串a长度为1。计算得next[1] 0因为j从-1开始i0时匹配i和j都变成0next[1]0。那么candidateLen 1 - 0 1。n % candidateLen 0成立。但一个长度为1的字符串由自身重复1次构成这通常不符合题目中“重复”的隐含意义重复通常意味着次数1。是否需要输出1完全取决于题目要求。candidateLen 0的判断至少能过滤掉candidateLen 0的退化情况虽然n % 0会除零错误但longestCommonLen不可能等于n所以candidateLen不会为0。更常见的处理是如果candidateLen n说明longestCommonLen 0字符串没有非平凡的前后缀肯定不是重复串应输出-1。所以更健壮的判断是if (candidateLen n n % candidateLen 0) { System.out.println(candidateLen); } else { System.out.println(-1); }条件candidateLen n确保了找到的周期长度严格小于字符串本身这符合“由更短前缀重复构成”的直观理解。边界条件测试务必用以下案例测试你的代码aaaa 应输出1由a重复4次构成。ababab 应输出2。abcabcabc 应输出3。abcde 应输出-1或5。a 根据题意输出-1单字符通常不认为是重复串或1。abacnext数组计算后candidateLen2但4 % 2 0然而abac并不是由ab重复构成的abab!abac。这里就暴露了我们算法的局限性这是一个非常重要的陷阱4.3 对算法局限性的深入思考与修正上述基于next[n]的判断if (n % (n - next[n]) 0)就得出周期结论的算法在网上广为流传但它实际上是不完全正确的它只是必要条件而非充分条件。反例就是s abac。n 4计算next数组过程略可用上述代码计算得到next[4] 1aba的最长相等真前后缀是a长度1。candidateLen 4 - 1 3。4 % 3 ! 0所以这个反例不会误判。我们需要一个更强的反例。让我们构造一个s abcab。n 5手工计算next数组对于abcabnext[0] -1next[1] 0(子串a)next[2] 0(子串ab前缀a和后缀b不同)next[3] 0(子串abc)next[4] 1(子串abca前缀a和后缀a相同长度1)next[5] 2(子串abcab前缀ab和后缀ab相同长度2)注意我们计算到了next[5]对应整个字符串。longestCommonLen next[5] 2candidateLen n - longestCommonLen 5 - 2 3n % candidateLen 5 % 3 2 ! 0。算法判断不是周期串正确。那有没有n % candidateLen 0但又不是周期串的例子呢有的比如s ababac。n 6计算next数组需要耐心next[0]-1next[1]0next[2]0next[3]1(aba前后缀a)next[4]2(abab前后缀ab)next[5]3(ababa前后缀aba)next[6]?我们来算整个ababac。真前缀和真后缀找最长相等 前缀a,ab,aba,abab,ababa后缀c,ac,bac,abac,babac没有相等的所以next[6] 0。longestCommonLen 0candidateLen 6 - 0 6n % candidateLen 0成立但candidateLen n根据我们candidateLen n的判断会输出-1。所以也没问题。看来if (candidateLen n n % candidateLen 0)这个条件在大多数情况下是有效的但它背后的理论支撑是什么其实有一个定理字符串s由长度为len的子串重复构成当且仅当len能整除n且s[i] s[i % len]对所有i成立。而next数组性质给出的是如果字符串是周期串那么n - next[n]一定是最小周期长度且n % (n - next[n]) 0。反之如果n % (n - next[n]) 0能否推出字符串是周期串不一定。但可以推出字符串具有某种“循环节”的性质但末尾可能有一个“残缺”的循环节。然而对于竞赛题尤其是蓝桥杯题目设计的测试用例往往比较“规整”使用这个条件通常能AC。但从严谨的角度我们应该在判断n % candidateLen 0之后再进行一次验证。4.4 严谨的、带有验证的完整解决方案为了确保万无一失我们应当在数学条件满足后显式地验证字符串是否真的由候选前缀prefix s.substring(0, candidateLen)重复构成。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s scanner.next(); int n s.length(); int[] next new int[n 1]; next[0] -1; int i 0, j -1; while (i n) { if (j -1 || s.charAt(i) s.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } int longestCommonLen next[n]; int candidateLen n - longestCommonLen; // 严谨判断1. 候选长度必须小于原串长度2. 原串长度必须是候选长度的整数倍 if (candidateLen 0 candidateLen n n % candidateLen 0) { // 验证阶段检查是否真的由该前缀重复构成 String prefix s.substring(0, candidateLen); boolean isRepeated true; for (int k candidateLen; k n; k candidateLen) { // 比较从k开始的candidateLen个字符是否等于prefix // 使用String.substring每次都会生成新对象对于大字符串可能效率稍低但可读性好。 // 也可以使用字符逐一比较。 if (!s.substring(k, k candidateLen).equals(prefix)) { isRepeated false; break; } } if (isRepeated) { System.out.println(candidateLen); } else { System.out.println(-1); } } else { System.out.println(-1); } scanner.close(); } }这个验证循环的时间复杂度是O(n)因为每个字符最多被比较一次。加上计算next数组的O(n)总复杂度仍是O(n)。虽然多了一次遍历但保证了算法的绝对正确性避免了因理解偏差或边界用例导致的错误。在竞赛中除非时间卡得极其严格否则这点开销是完全可以接受的并且能换来AC的稳定性。5. 性能优化与空间考量对于算法竞赛我们还需要关注代码的效率和内存使用。5.1 避免不必要的字符串截取上面的验证循环中我们使用了s.substring(k, k candidateLen).equals(prefix)。在Java中substring方法在较新版本中虽然通常是共享底层字符数组但依然会创建一个新的String对象。对于极端情况如n10^6 candidateLen很小这可能会创建大量对象增加GC压力。更高效的做法是直接比较字符boolean isRepeated true; for (int k 0; k n; k) { if (s.charAt(k) ! s.charAt(k % candidateLen)) { isRepeated false; break; } }这个循环直接验证了周期串的定义每个位置的字符必须等于s[位置 % 周期长度]的字符。它完全避免了子串对象的创建效率更高。5.2 空间优化我们使用了一个长度为n1的int数组next。对于n高达10^6的情况这需要大约4MB的内存一个int4字节在Java竞赛环境通常内存限制256MB或512MB中是完全可以接受的。几乎不需要在这方面进行优化。如果一定要优化可以考虑使用char数组存储字符串并用int数组存储next值这已经是比较标准的做法了。5.3 输入输出优化对于Java选手在蓝桥杯等竞赛中当数据量很大时比如n接近10^6使用Scanner读取字符串可能比BufferedReader稍慢但通常也够用。如果追求极致速度可以使用BufferedReaderimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String s br.readLine().trim(); // 注意题目可能包含换行符 // ... 后续算法代码 } }输出使用System.out.println即可通常不是瓶颈。6. 举一反三相关变种问题与解题思路掌握了“重复字符串”的核心解法后我们可以解决一系列变种问题。这体现了算法思维的迁移能力。6.1 变种一求字符串的最大重复次数题目可能问给定字符串s它是由某个子串t重复k次连接而成求最大的k。 解法先求出最小周期长度len用上述方法。如果字符串是周期串即验证通过那么最大重复次数k n / len。否则k 1字符串自身。6.2 变种二构造重复字符串题目给定一个字符串s你可以在其末尾添加最少的字符使得新字符串变成一个由某个子串重复构成的字符串。求需要添加的最少字符数。 思路先找到字符串的“循环节”特征。计算next数组得到candidateLen n - next[n]。如果n % candidateLen 0说明它已经是周期串无需添加。否则它有一个“残缺”的循环节。缺失的长度就是candidateLen - (n % candidateLen)。例如sabcabn5,next[5]2,candidateLen3。5 % 3 2所以缺失3-21个字符。我们需要添加s[0]即a到末尾得到abcaba它是由abc重复2次abcabc的前5个字符不abcaba并不是周期串。更准确地说我们需要添加字符使得总长度是candidateLen的倍数且添加的字符必须符合周期规律。添加的字符应该是前缀s[0:缺失长度]。但这里要小心因为s本身可能不是周期串这个candidateLen只是基于next数组的推测最终添加后是否能形成周期串可能需要验证。这类问题更稳妥的做法是枚举所有可能的周期长度n的因子然后检查并计算需要修改或添加的字符数求最小值。这引出了下一个变种。6.3 变种三重复字符串的编辑距离问题题目给定字符串s你可以进行修改替换字符、删除、插入操作问最少操作多少次能让字符串变成某个子串重复k次k可以大于1的形式。 思路这个问题难度较大。一种思路是动态规划。定义dp[i][j]表示考虑s的前i个字符且当前重复单元长度为j时的最小操作次数。但状态转移复杂。另一种近似思路是枚举所有可能的周期长度len1到n对于每个len将字符串按周期长度分段统计每列即所有第len模意义下同余的位置上出现次数最多的字符将其他字符改为该字符的成本就是修改操作数。这可以解决“只允许替换”操作的问题。如果允许插入和删除则问题更接近“寻找与某个周期串的最短编辑距离”可以用DP求解。6.4 在真实场景中的应用这种寻找字符串周期的算法不仅仅用于解题。在数据压缩如游程编码的扩展、网络协议数据帧的同步、生物信息学DNA序列的重复模式识别中都有应用。例如在文件系统中检测一个文件是否由大量重复的块组成可以用于简单的数据去重分析。7. 调试技巧与常见错误排查在实现这个算法时即使理解了原理也容易在代码中犯错。下面分享几个调试技巧。7.1 next数组计算错误的调试next数组的计算是KMP的难点也是容易出错的地方。建议对于短字符串如abab,abcab手动模拟算法过程并与你的代码输出对比。可以在计算过程中加入打印语句while (i n) { if (j -1 || s.charAt(i) s.charAt(j)) { i; j; next[i] j; System.out.println(i i , j j , next[ i ] next[i]); // 调试输出 } else { j next[j]; System.out.println(回溯: j next[ j ]); // 调试输出 } }对比你的手动计算过程看哪里不一致。7.2 周期验证失败的调试如果你的代码在某个测试用例上输出错误首先单独测试周期验证部分。写一个简单的函数给定字符串s和候选长度len验证是否成立。用错误的用例去测试它。例如对于abaclen2如果错误地得出这个候选验证函数应该返回false。确保你的验证逻辑是正确的。7.3 边界条件处理务必测试以下边界空字符串如果题目允许通常长度为零的字符串其周期定义是模糊的按题目要求处理。单字符字符串如a根据题目要求判断是否输出1或-1。全相同字符的字符串如aaaa应输出1。完全没有重复模式的字符串如abcde应输出-1或n。长度很大的字符串在本地生成一个1e6长度的周期串测试程序是否超时或内存溢出。7.4 内存与性能分析使用Java VisualVM或简单的打印时间戳的方式测试你的算法在大数据下的表现。确保没有意外的时间复杂度退化如验证循环中嵌套了不必要的操作。对于n1e6O(n)的算法应该在几十毫秒内完成。这道“重复字符串”题目表面上是考察字符串处理内核是考察对KMP算法next数组深刻理解的经典问题。从暴力枚举到KMP优化从粗略的next性质到严谨的验证我们一步步剖析了问题的本质和解决方案的演进。在竞赛和工程中这种“识别问题模式 - 应用经典算法 - 注意边界验证”的思维链条至关重要。希望这篇详细的拆解不仅能帮你AC这道蓝桥杯真题更能让你掌握这种解决一类问题的能力。下次看到“周期”、“循环”、“重复子串”这些关键词时你会立刻想到先算一下next数组看看。