如何判断字符串是否由重复子串构成？（LeetCode 459）

简化版

判断字符串 s 能否由它的某个子串重复多次拼成（如 "abab" = "ab"×2，"abcabcabc" = "abc"×3）。有一个非常巧妙的技巧：把 s 和 s 拼成 s + s，掐掉首尾各一个字符，看剩下的中间部分是否还包含 s——若包含，说明 s 有重复结构。即 (s + s).substring(1, 2n-1).contains(s) 为 true 则是。另一种是用 KMP 的 next 数组判断。

详细版

解法一：拼接技巧（一行核心）

boolean repeatedSubstringPattern(String s) {
    String doubled = s + s;
    // 去掉首尾各一个字符后，若仍包含 s，则 s 由重复子串构成
    return doubled.substring(1, doubled.length() - 1).contains(s);
}

解法二：KMP next 数组

boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    int[] next = buildNext(s);           // next[i] = 最长相等真前后缀长度
    int len = next[n - 1];               // 整个串的最长相等前后缀
    // 若 len > 0 且 n 能被「最小重复单元长度 (n - len)」整除 → 有重复结构
    return len > 0 && n % (n - len) == 0;
}

拼接技巧：s+s 去头尾后含 s ⟺ s 有循环节。O(n)（contains 可用 KMP 达线性）。
KMP 法：最小重复单元长度 = n - next[n-1]，若它能整除 n 且 next[n-1]>0，则由重复子串构成。
复杂度：两法都可做到 O(n)。

完整版教学

一、题意：s 是否有「循环节」

问 s 能不能写成某个子串 t 重复 k 次（k ≥ 2）。这个 t 叫最小重复单元（循环节）。比如 "abcabc" 的循环节是 "abc"（重复 2 次），"aaaa" 的循环节是 "a"（重复 4 次）。要判断是否存在这样的循环节。

二、解法一：s+s 掐头去尾的妙招

技巧是：判断 s + s 去掉首尾各一个字符后，是否仍包含 s。

为什么成立？ 直觉理解：

如果 s 由循环节 t 重复 k 次构成（k≥2），那么 s + s 就是 t 重复 2k 次。去掉首尾各一个字符后，中间仍然完整包含着「t 重复 k 次」= s 的副本（因为循环节多、错开一个位置还能对齐）。所以 contains(s) 为 true。
反过来，如果 s 没有循环节（不能由更小单元重复），那么 s 在 s+s 中只会出现在开头和末尾两个位置（下标 0 和 n）。掐掉首尾各一个字符正好破坏了这两个位置，中间再也找不到 s，contains(s) 为 false。

关键点：s + s 里 s 出现的位置，恰好反映了 s 的「自相似周期」。掐头去尾是为了排除「s 本身在 0 和 n 的平凡出现」，只留下「因循环节而产生的额外出现」。

三、为什么掐掉的是「首尾各一个」

s + s 长度 2n，s 一定出现在下标 0（前半个 s）和下标 n（后半个 s）。我们要检测的是「有没有在其他位置也出现 s」——那才意味着循环节。

去掉首字符（下标 0）→ 破坏了下标 0 处 s 的出现。
去掉尾字符（下标 2n-1）→ 破坏了下标 n 处 s 的出现（它的最后一个字符在 2n-1）。

于是 substring(1, 2n-1) 里只有「非平凡位置」的 s。若还能找到 s，就证明存在错位对齐的循环节。这就是「首尾各一个」的精确用意——不多不少，恰好剔除两个平凡出现。

四、解法二：KMP 的 next 数组

更「有理有据」的方法用 KMP 前缀表。设 next[n-1] = 整个串 s 的最长相等真前后缀长度 len。那么 n - len 就是 s 的最小重复单元的候选长度。

判断：len > 0 && n % (n - len) == 0。

原理：如果 s 有循环节，其最长相等前后缀会「错开一个循环节」地重叠，n - len 恰好等于循环节长度，且 n 能被它整除（重复整数次）。len > 0 排除「无任何重复」的情况。这个结论是字符串周期性的经典定理（弱周期引理的应用）。

五、两种解法怎么选

	拼接技巧	KMP next
代码	极短、好记	要写 next 数组
原理	直觉但要想清「首尾各一」	严谨，靠周期定理
复杂度	O(n)（contains 用 KMP）	O(n)

面试策略：拼接技巧一行就能写，但要能解释「为什么去首尾、为什么成立」；KMP 法能体现对 next 数组周期性质的理解。两个都值得会，理解拼接法的原理是加分点。

六、从周期长度验证两种判据

若字符串长度 n 由长度 p 的片段重复，左移 p 位后的字符串仍与原串相同；s+s 正好包含所有循环位移。掐掉首尾字符排除零位移对应的原位置后，仍能找到 s，就说明存在非零且小于 n 的循环位移，也就是存在真周期。

s="abab", n=4, 最短周期 p=2
s+s = "abababab"
去掉首尾字符得到 "bababa"
其中从下标 1 可找到 "abab"
KMP: lps[3]=2
候选周期 n-lps=2，且 4%2=0
两种判据都成立

校验维度	本题必须保持的结论
循环/递推不变量	KMP 判据中的 `n-lps[n-1]` 是最短候选周期；只有整除 n 才能完整铺满字符串。
边界条件	长度 1 不可能由更短非空子串重复；KMP 必须要求最长边界长度大于 0。
复杂度与代价	`contains` 是否线性取决于库实现；KMP 明确 O(n) 时间 O(n) 前缀表空间。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：KMP 判据中的 n-lps[n-1] 是最短候选周期；只有整除 n 才能完整铺满字符串。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“s=“abab”, n=4, 最短周期 p=2”开始手推，最后应得到“两种判据都成立”。
边界复核：长度 1 不可能由更短非空子串重复；KMP 必须要求最长边界长度大于 0。
代价复核：contains 是否线性取决于库实现；KMP 明确 O(n) 时间 O(n) 前缀表空间。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“KMP 判据中的 n-lps[n-1] 是最短候选周期；只有整除 n 才能完整铺满字符串。”这条正确性主线不能省。

八、常见误区与追问

误区：只要存在非空相等前后缀就一定是重复串。 abcab 有边界 ab，但候选周期 3 不能整除长度 5。
误区：直接判断 s 是否出现在完整的 s+s 中。 它必然在起点 0 和 n 出现，必须排除这两个平凡位置。
误区：候选周期就是 lps[n-1]。 周期长度是 n-lps[n-1]，lps 表示重叠边界长度。
追问：为什么整除条件不可少？ 不能整除时候选片段只能覆盖若干整段加残段，无法由同一子串完整重复。
追问：字符串 aaaa 的最短周期是多少？ lps 最终为 3，4-3=1，由 a 重复 4 次。
追问：两倍字符串法会增加多少空间？ 显式构造拼接串需要 O(n) 额外空间，KMP 也需 O(n) 前缀表。

九、加强记忆

判断字符串由重复子串构成 = 判断 s 有无循环节。拼接技巧：(s + s) 掐掉首尾各一个字符后仍 contains(s) ⟺ 有循环节——因为 s 在 s+s 中平凡出现在下标 0 和 n，去首尾恰好剔除这两处，还能找到 s 就说明存在错位对齐的循环节。KMP 法：len = next[n-1]，最小循环节长 = n - len，当 len > 0 && n % (n-len) == 0 即是。两法都 O(n)。核心记住那个妙招：s+s 去头尾，还含 s 就有循环节。

简化版

详细版