1. 题目到底在问什么从重复构造说到字符串周期做字符串专题的时候我第一眼看到重复的子字符串这道题脑子里冒出的念头很简单这不就是检查一个串是不是复制粘贴出来的吗但真正动手写代码之后才发现题目越短坑越隐蔽。把这道题完全吃透至少能带出两个以后经常用到的字符串概念——周期period和 border真前后缀所以这篇笔记我想把怎么做、为什么这么做、还有哪些坑一次说清楚。题意一句话给定一个非空字符串 s判断它能不能由自己的某个子串重复多次构成。三个典型例子先摆出来abab → true是 ab 重复 2 次aba → false中间那个 a 怎么对齐都不对abcabcabcabc → true可以看成 abc 重复 4 次也可以看成 abcabc 重复 2 次。如果只是刷题过个瘾看懂例子就够了。但要是想稳稳通过并且面试能讲清楚下面这三个隐含条件必须刻在脑子里。1.1 三个容易被忽略的题目约束第一这个子串必须是字符串的前缀。因为整个串是它复制出来的开头位置一定是它自己不可能开头是别的东西。这一点在暴力枚举时决定了我们只需要检查s[:L]这种前缀块而不是任意位置的子串搜索空间一下就小了很多。第二子串长度必须整除整个字符串长度。n 个字符要切成若干段完全相同的块每块长度必须一模一样也就是说块长 L 必须是 n 的因数。这个条件看似简单却是后面枚举法剪枝的核心也是判断看起来有周期但拼不成完整串的关键。第三至少要重复2 次。这意味着 L 最大只能取到 n // 2而且长度为 1 的字符串直接就是 false。很多人写第一版代码时会把自己重复一次也算进去结果任何字符串都返回 true这就是没把重复多次这个语义想清楚。顺带一提题目明确说了输入是非空字符串所以空串这个边界不需要处理但你要是写工具函数建议还是留一手判断省得到时候被奇怪的输入坑到。1.2 这道题的本质找一个合格的周期 d再从理论层面往深走一步。计算机科学里管字符串按某个固定间隔平移后仍然自洽这件事叫周期period如果对所有合法的 i 都有s[i] s[i d]就说 d 是 s 的一个周期。注意周期 d 并不要求整除 n。这个不要求整除最典型的例子是 abcab。它满足s[0] s[3]都是 a、s[1] s[4]都是 b所以 3 是它的周期。但 3 不整除 5它没法切成整数个长度 3 的块于是abcab不是任何子串的重复拼接——它只是首尾碰巧长得像中间接不上。还有一个对称的概念叫border一个子串同时是 s 的真前缀和真后缀就叫 border。比如 abab 的 border 是 ab长度 2abcab 的 border 也是 ab。border 的长度直接关系到后面 KMP 解法的正确性。把这两个概念放在一起题目就翻译成了这样一句话判断 s 是否存在一个合法的周期 d满足 d 整除 n、且 d 小于 n至少分成两份。后面所有解法本质上都是在用不同手段寻找这个 d。想明白这一层再去看代码就不会觉得是玄学了。我强烈建议先亲手推三五个例子再动键盘字符串题的失分点往往不是算法不会而是对题意半懂不懂就开始写循环。提示做题前在草稿纸上写下三个必要条件——长度整除、块是前缀、至少两块。后面验证任何解法都拿这三条去套。2. 枚举分频法用整除性砍掉大部分无效搜索最直白的做法其实就是模拟定义如果 s 能由长度 L 的块重复构成那么 L 一定在 1 到 n // 2 之间并且 L 必须整除 n。枚举 L跳过所有不整除的剩下的候选逐个验证这就是枚举分频法的全部逻辑。2.1 先按定义写出第一版def repeated_substring_pattern(s: str) - bool: n len(s) for L in range(1, n // 2 1): if n % L ! 0: continue pattern s[:L] if pattern * (n // L) s: return True return False这段代码我之所以喜欢是因为它把定义原封不动翻译成了程序pattern 取前缀乘上 n // L 次再跟原串整体比较。Python 的字符串乘法会精确构造出一个长度为 n 的新串比较结果一目了然几乎不可能写错。但如果你用 C 或者 Java字符串乘法没那么方便就得换一种等价写法——既然每一块都相同那么第 i 个位置的字符必然和第 i - L 个位置的字符相等相当于把整个串按块长 L 做了一次错位对齐。2.2 逐位对齐的等价写法def repeated_substring_pattern(s: str) - bool: n len(s) for L in range(1, n // 2 1): if n % L ! 0: continue ok True for i in range(L, n): if s[i] ! s[i - L]: ok False break if ok: return True return False两层循环看起来像 O(n²)但实际远远达不到这个量级。外层真正进入验证的只有 n 的因数而 n 的因数个数非常少数学上约等于 O(n^(1/3))就算 n 取到 10^5因数个数也就一百上下。每个候选最坏需要扫描一遍字符串所以总代价大约是 O(n × τ(n))τ(n) 是因数个数。以题目通常给的数据范围字符串长度 10^4 级别来看Python 都能轻松跑过更别说底层更快的 C 了。这里还要说明白一件事外层循环本身确实会跑 n // 2 次取模运算但取模是 O(1) 的只是整数运算不涉及扫描字符串所以这部分开销可以忽略不计。复杂度分析时要把循环次数和真正做字符串比较的次数分开看别一看到嵌套循环就喊 O(n²)。2.3 正确性从哪来三条判断准则面试时如果被问凭什么这个暴力算法是对的我会按下面三条讲条理非常清晰必要性若 s unit^k 且 k ≥ 2那么 len(unit) 必然整除 nunit 恰好等于 s 的前 len(unit) 个字符且 len(unit) ≤ n / 2。充分性反过来只要某个 L 满足整除条件并且s s[:L] * (n // L)那么按定义 s 就是由子串 s[:L] 重复构成。为什么跳过不整除的 L 是安全的块长不整除 n 时n 个字符不可能切成整数个相同块长度都对不上验证必然失败。把这三条讲完面试官基本能确认你是真的理解而不是背代码。还有一个值得养成的习惯从小到大枚举 L。如果题目有一天改成找出最短重复子串从小到大枚举会在第一个合法 L 处返回拿到的就是最小周期本题虽然只要求布尔值但这个习惯在别的题里能直接救命。举个例子aaaa 你既可以说块长 1也可以说块长 2只有从小到大枚举才能稳定给出最小块长 1。3. 一行拼接查找法s 藏在 (ss)[1:-1] 里的数学解释接下来这个解法我第一次看到的时候直呼离谱因为它的完整代码只有一行def repeated_substring_pattern(s: str) - bool: return s in (s s)[1:-1]意思是把 s 拼上自己掐头去尾去掉最前面和最后面各一个字符在剩下的字符串里查找 s能找到就说明 s 是重复串。这一节我要把为什么能这样的正反两个方向都推一遍因为面试里这个解法最容易被追问也是我最常看到有人讲错的地方。3.1 正向推演为什么重复串一定藏在中间先看充分性如果 s 真的是重复串设 s unit^kk ≥ 2。那么 s s 就是 unit 的 2k 份拼接。去掉第一个字符打碎的是第一份 unit去掉最后一个字符打碎的是最后一份 unit。中间剩下的部分是连续的 2k - 2 份完整 unit。因为 k ≥ 2所以 2k - 2 ≥ k也就是说中间这段的长度足够装下整整一个 s也就是 k 份 unit。于是 s 必然作为连续子串出现在(ss)[1:-1]里。边界情况 k 2 时2k - 2 2 k刚好够放不多不少。比如 ababss abababab掐头去尾变 bababaabab 正好出现在偏移 1 的位置。3.2 反向推演找到它为什么就能判定可重复反方向才是这个 trick 真正巧妙的地方如果 s 确实出现在中间串里为什么就一定能推出 s 是重复串这里有一个特别容易踩的 off-by-one 陷阱我必须先说清楚。设T (ss)[1:-1]它的第 k 个字符对应的是 ss 的第 k1 个字符。如果 s 在 T 中匹配的起始下标是 i0 ≤ i ≤ n-2那么 s 的第 j 个字符等于(ss)[ij1]也就是s[j] s[(i j 1) % n] 对任意 j 成立令 d i 1因为 i 的取值范围是 0 到 n-2所以 d 恰好落在 1 到 n-1 之间。于是上面的等式变成s[j] s[(j d) % n]意思是把 s 首尾相接看成一个环整体平移 d 位之后和原来完全一样。接下来是关键一步。设 g gcd(d, n)因为 d 和 n 的最大公约数可以通过线性组合表示即存在整数 a、b 使得 a·d b·n g所以平移 d 位不变反复作用下去就等价于平移 g 位不变。也就是说s 每隔 g 个字符就重复一次。而 g 整除 n且 g ≤ d n所以 s 就是前缀 s[:g] 重复 n // g 次构成的s 当然是重复串。反方向证毕。还是用 abab 验证一遍ss ababababT bababaabab 在 T 中的起始下标是 1所以 d 2gcd(2, 4) 2周期 2 正好对应 ab 这个块。如果谁把下标算错成 d i就会得到 gcd(1, 4) 1推出 abab 是 aaaa矛盾立刻暴露。3.3 使用场景与面试风险这个一行解的隐藏成本值得说一下Python 的in操作符对字符串用的是高效子串搜索算法理论上是线性复杂度所以代码本身很快。但换到其他语言就不一定了Java 的contains、C 的find底层实现各不相同而且面试官大概率会追问你确定它一定能正确判断吗。我见过不少人只能背出这行代码却讲不出上面这通推导结果被问得当场卡住。所以我的建议是这个解法适合当加分技巧展示但别当主解。如果真要在白板上手推枚举法和 KMP 才是你能掌控全场的选择。另外记住两个常见错误一是写成s in s s这当然恒为 trues 自己就是 ss 的子串谁都能找到二是只掐头不掐尾或者切片边界写错导致判断结果不稳定。必须严格是头尾各去掉一个字符才成立。4. KMP 前缀函数解法最长 border 如何反推最小周期这一节是整道题的精华也是我建议每个刷字符串专题的人都必须掌握的解法。前面枚举法是在暴搜周期 d拼接法是在利用周期带来的环状性质而 KMP 的思路完全不同它通过计算整个串的最长 border 长度直接反推周期。4.1 前缀函数的构建逻辑与手工跟踪先回忆前缀函数也叫 next 数组、pi 数组pi[i]表示子串 s[0..i] 的最长真前缀等于真后缀的长度。这里真的意思是长度最多到 i不能等于子串本身。一个串所有既是前缀又是后缀的子串统称 border所以pi[i]就是 s[0..i] 的最长 border 长度。标准构建代码如下def build_pi(s: str) - list: n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] # 上一轮的最长 border 长度 while j 0 and s[i] ! s[j]: j pi[j - 1] # 尝试更短的 border if s[i] s[j]: j 1 pi[i] j return piwhile 回退逻辑是新手最容易绕晕的地方。我建议手动跟一个例子s ababc。i 1字符 b。j 从 pi[0] 0 开始s[1] ! s[0]pi[1] 0。i 2字符 a。j 从 pi[1] 0 开始s[2] s[0]j 变成 1pi[2] 1。i 3字符 b。j 从 pi[2] 1 开始s[3] s[1]j 变成 2pi[3] 2。i 4字符 c。j 从 pi[3] 2 开始s[4] ! s[2]于是 j 回退到 pi[1] 0再比较 s[4] ! s[0]pi[4] 0。最终 pi [0, 0, 1, 2, 0]。i 3 时的 2 表示 abab 的最长 border 是 abpi[4] 0 表示 ababc 整体没有任何 border。4.2 从 pi[n-1] 到候选周期border 与周期之间的桥算完整串的前缀函数后看最后一个值pi[n-1]它表示整个 s 的最长 border 长度。直觉是这样的如果 s 是由某个块重复出来的那么除了最后一个块前面所有部分拼起来就恰好是一个很长的 border——它同时是前缀前 k-1 个块也是后缀后 k-1 个块。拿 ababab 验证n 6手动算 pi [0, 0, 1, 2, 3, 4]pi[5] 4即 abab 是 ababab 的真前缀也是真后缀。此时border 没覆盖住的那段长度是 n - pi[n-1] 2正好等于重复块 ab 的长度。再看一个更长的例子 abaababaab它等于 abaab 重复 2 次。算出来的 pi[9] 5n - pi 5正是块长。这说明什么当 s 确实是重复串时n - pi[n-1] 就是那个重复块的长度。这条性质在很多字符串教材里都有是 border 理论的核心结论如果 n 能被 n - pi[n-1] 整除那么 s 由前缀 s[:n-pi[n-1]] 重复构成并且这个长度就是最小周期。反过来如果 s 是重复串则整除必然成立。4.3 为什么必须加整除判断abcab 反例但border 长不等于一定是重复串。最经典的反例是 abcab它的 pi[4] 2border 是 abn - pi[n-1] 3。3 确实是 abcab 的一个周期字符隔 3 位相等但 3 不整除 5所以这串没法切成整数个长度 3 的块它根本就不是重复串。因此最终判断条件必须同时满足两个要求候选周期p n - pi[n-1]必须小于 n且 n 必须被 p 整除。写成完整代码def repeated_substring_pattern(s: str) - bool: n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and s[i] ! s[j]: j pi[j - 1] if s[i] s[j]: j 1 pi[i] j p n - pi[-1] return p n and n % p 0这里的p n极其关键。如果漏掉长度为 1 的 a 会算出 pi [0]、p 1然后 1 % 1 0错误地返回 true。有了p n守卫单字符串和不重复的串都会被拦下来。C 版长得几乎一样bool repeatedSubstringPattern(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; } int p n - pi[n - 1]; return p n n % p 0; }复杂度稳定 O(n)空间 O(n)。这也是为什么 KMP 是这题的最优解它把找周期这件事压缩成了一次线性扫描不需要像枚举法那样反复验证多个候选长度。5. 边界用例与踩坑记录这些 case 必须全部过刷题最怕的不是大思路不对而是小边界翻车。我在做这道题时实际踩过的坑、以及评论区见过别人踩的坑整理成下面这份清单。5.1 十组自查用例与逐条要点先把必须跑对的用例列成表输入期望输出说明ababtrue最基础的重复串块长 2abafalse有周期幻觉但长度不整除abcabcabctrue块长 3重复 3 次afalse长度 1不可能重复两次abfalse块长只能取 1验证失败aatrue块长 1重复 2 次的最小例子aaatrue块长 1重复 3 次abcabfalse有周期但块长不整除长度abababtrue块长 2重复 3 次也可当块长 3abaababaabtrue块长 5重复 2 次逐个核对时的重点单字符 a最容易漏掉的是p n的判定。KMP 法里 pi[-1] 0p n此时 n % p 0 恒成立没有p n守卫就会错。枚举法因为循环上界是 n // 2天然排除了 L n反而更安全。abcab 这类部分周期串它有 border ab也有周期 3但拼不成完整重复串。KMP 靠整除判定拦截枚举法靠 n % L 拦截。任何少了整除判断的 KMP 实现在这个用例上必挂。ababab 多重周期ab 能拼abab 也能拼看成两个块。本题只要求返回布尔值任意一个命中都算对。只有题目改成求最小重复单元时才需要关心输出是 2 还是 3。aa、aaa 最小重复情况枚举法 L 1 命中KMP 里 pi[n-1] n-1p 1整除成立。aa 的 pi [0, 1]p 11 2 且 2 % 1 0正确。拼接法对长度 2 的串aa 经过(ss)[1:-1]得到 aa查得到trueab 得到 ba查不到false。这个细小的对比能验证你对拼接法是否理解到位。5.2 两个隐蔽的代码级坑第一个坑在前缀函数的 while 条件里while j 0 and s[i] ! s[j]必须把j 0写在前面。Python 短路求值保证 j 为 0 时不会访问s[j]一旦顺序写反字符串访问越界是小事Python 里s[-1]还会悄悄取到最后一个字符结果完全错乱且不报错这种 bug 难排查得很。第二个坑是 C 的size_t。s.size()返回无符号类型直接参与n - pi[n-1]和%运算时无符号数之间的运算结果还是无符号的某些表达式会隐式转换成奇怪的大数再强转回 int 就可能出现莫名其妙的错误。稳妥做法是一开始就写int n (int)s.size();。最后分享一个习惯把测试用例写成参数化循环本地一键跑完所有 case 再提交。字符串题尤其值得这样做因为肉眼检查边界太容易漏了。我通常会在本地脚本里直接把上面十组数据喂进去任何解法写完先过一遍确认全绿才上提交页。6. 面试表现与方案取舍先讲什么、再讲什么如果你是在面试现场遇到这题我建议的答题节奏是先给出最容易讲清楚、几乎不会出错的枚举法再主动抛出 KMP 的 O(n) 解法最后如果时间充裕或面试官吃这一套再展示拼接查找的一行解并讲透背后的环状平移证明。6.1 三种方案放在一起比方案时间复杂度空间复杂度代码量讲解难度适用场景枚举分频O(n·τ(n))实际接近 O(n)O(1) 或 O(n)很短最低直接用定义面试第一版、笔试快速通过拼接查找平均 O(n)O(n)一行需要完整证明两个方向秀技巧、追求极简代码KMP 前缀函数O(n)O(n)中等需要理解 border 概念面试最优解、延伸题的基础如果被追问你能证明为什么 pi[n-1] 对应的周期一定是最小周期我一般这样组织回答先指出pi[n-1]意味着前缀和后缀有一段长度为它的相等区域令 p n - pi[n-1]。当 n % p 0 时把 s 按长度 p 切成 n/p 块相邻两块的重叠部分恰好是同一个 border 的左右两端由归纳可以证明每一块都相等。要是 s 还有更小的周期 q那么至少存在长度 n - q 的 border而 q p 会推出 n - q n - p pi[n-1]与 pi[n-1] 是最大值矛盾。这个回答不用写得像论文但能传达出我不是背模板的信号。还有一个小提醒不要主动提正则表达式解法。像(.?)\1这种写法理论上是可行的但正则引擎的回溯在最坏情况下很慢而且这题跟正则匹配的语义有微妙差别在面试里拿出来只会让面试官觉得你在绕路。6.2 前缀函数不止服务于这一题很多人觉得 KMP 解法为了一个简单题学这么重的东西不划算我的看法恰恰相反。前缀函数是一个可以复用的底层工具后面你遇到字符串匹配、最短回文串、重复次数统计、周期串判断、子串出现次数这些题目时都会再次用到它。把 ababc 的手工推演做过一遍之后你对 KMP 的理解就不再是背代码了而是真正知道 j 回退时发生了什么——这比多刷十道简单题都有价值。6.3 一点个人体会这道题给我最大的收获是让我彻底接受了字符串题的难点不在代码而在把隐含条件翻译成程序能判断的显式条件这个观点。你看这三种解法枚举法在显式地找整除 n 的候选周期 d拼接法在利用 d 带来的环状自洽性质KMP 在从 border 长度反推 d——表面上完全不同的三条路底层其实是同一个数学对象。做题做到这一步才算真正把题目吃透而不是记住了一个答案。