重复子串模式 题目描述 给定一个字符串 s ，检查它是否可以通过由其一个子串重复多次构成。例如，字符串 "abab" 可以由子串 "ab" 重复两次构成，返回 true；而字符串 "aba" 无法通过重复某个子串构成，返回 false。 解题过程 问题分析 我们需要判断字符串 s 是否由某个子串重复多次构成。关键点在于： 如果 s 可以由子串 t 重复 k 次构成（ k >= 2 ），那么 s 的长度一定是 t 长度的整数倍。 将两个 s 连接在一起形成新字符串 s2 ，并去掉首尾字符后，如果 s 仍然是 s2 的子串，则说明 s 满足重复子串模式。 哈希思路 使用滚动哈希（Rabin-Karp 算法思想）来高效判断子串匹配。我们可以计算 s 的哈希值，并在双倍字符串中寻找匹配，避免逐个字符比较。 具体步骤 设字符串 s 的长度为 n 。 将 s 与自身连接，得到新字符串 s2 = s + s ，然后去掉 s2 的首尾字符（即取 s2[1 : 2*n-1] ），得到字符串 s2_sub 。 在 s2_sub 中查找是否包含子串 s 。如果包含，则返回 true；否则返回 false。 使用滚动哈希优化子串查找过程： 选择基数 base 和模数 mod （例如 base=131 , mod=10^9+7 ）。 计算 s 的哈希值 target_hash 。 计算 s2_sub 的滚动哈希，并在滑动窗口中比较哈希值是否相等（需处理哈希冲突）。 示例 以 s = "abab" 为例： n = 4 , s2 = "abababab" , s2_sub = "bababa" 。 在 "bababa" 中查找 "abab" ，发现包含（从索引 1 开始匹配），返回 true。 以 s = "aba" 为例： n = 3 , s2 = "abaaba" , s2_sub = "baab" 。 "baab" 中不包含 "aba" ，返回 false。 复杂度分析 时间复杂度：滚动哈希可在 O(n) 时间内完成匹配。 空间复杂度：O(1)（除存储字符串外）。 关键点 双倍字符串去首尾的技巧将问题转化为子串匹配。 滚动哈希避免逐个字符比较，提升效率。