重复子串 题目描述 给定一个非空字符串 s ，检查它是否可以通过由它的一个子串重复多次构成。例如，字符串 "abab" 可以由子串 "ab" 重复两次构成，返回 true ；而 "aba" 无法通过重复某个子串构成，返回 false 。 解题过程 1. 问题理解 题目要求判断整个字符串 s 是否能被其某个 真子串 （长度小于 s ）重复多次拼接而成。关键点在于： 重复子串的长度必须是 s 长度的约数。 重复子串需要连续重复多次恰好填满 s 。 2. 暴力思路（哈希加速） 一种直接的方法是枚举所有可能重复子串的长度 len （ 1 ≤ len ≤ n/2 ，且 n % len == 0 ），然后检查每段长度为 len 的子串是否完全相同。 但直接逐字符比较效率较低，我们可以用 字符串哈希 来加速子串的比较。 字符串哈希 ：将字符串映射为一个整数，使得我们可以用 O(1) 时间比较两个子串是否相等。常用多项式滚动哈希（Rabin-Karp 思想）： 选择基数 base （如 131）和模数 mod （大素数）。 预处理前缀哈希数组 hash[i] 表示 s[0..i-1] 的哈希值。 计算子串 s[l..r] 的哈希值为： \[ H(l, r) = (hash[ r+1] - hash[ l ] \times base^{r-l+1}) \mod mod \] 需要预处理 base 的幂次数组 pow_base[] 。 3. 算法步骤 计算字符串长度 n 。 枚举可能的重复单元长度 len ，从 1 到 n/2 ，且满足 n % len == 0 。 计算整个字符串的哈希值，并检查是否每段长度为 len 的子串哈希值都相同。 第一段子串哈希值为 H(0, len-1) 。 第 k 段子串哈希值为 H((k-1)*len, k*len - 1) 。 若所有段哈希值相等，则返回 true 。 如果所有 len 都不满足，返回 false 。 4. 举例说明 以 s = "abab" 为例： n = 4 ，枚举 len = 1 和 len = 2 （ n/2=2 ）。 len = 1 ：每段应为 "a" ，但第二段是 "b" ，不匹配。 len = 2 ：每段应为 "ab" ，比较： 第一段 "ab" ，第二段 "ab" ，匹配，返回 true 。 5. 优化与细节 哈希可能冲突，可以用双哈希（两个不同的 base 和 mod ）降低概率。 另一种巧妙解法：将 s 拼接成 s + s ，然后去掉首尾字符，检查原字符串 s 是否出现在新字符串中（KMP 或直接包含判断）。原理是如果 s 由重复子串构成，那么 s 会在 (s+s)[1:-1] 中出现。 时间复杂度：枚举约数 + 哈希比较，总体接近 O(n)。