重复子串模式 题目描述 给定一个非空字符串 s ，检查它是否可以通过由其一个子串重复多次构成。例如： 输入 "abab" ，返回 true （可由 "ab" 重复两次构成）； 输入 "abcabcabc" ，返回 true （可由 "abc" 重复三次构成）； 输入 "abac" ，返回 false （无法由子串重复构成）。 解题思路 暴力枚举子串长度 子串长度 len 必须是字符串长度 n 的约数，且子串长度最大为 n/2 （因为至少重复一次）。 对于每个可能的子串长度 len ，取出前 len 个字符作为模式串，检查后续每 len 个字符是否都与模式串相同。 哈希优化（Rabin-Karp 思想） 计算字符串的哈希值，通过滚动哈希快速比较子串是否相同，避免逐字符比较。 具体步骤： a. 计算整个字符串的哈希值。 b. 对于每个可能的子串长度 len ，计算前 len 个字符的哈希值 pattern_hash 。 c. 用滚动哈希计算后续每个长度为 len 的子串的哈希值，与 pattern_hash 对比。 详细步骤（以哈希优化为例） 步骤 1：枚举子串长度 设字符串长度为 n ，子串长度 len 需满足 n % len == 0 ，且 1 ≤ len ≤ n/2 。 例如 s = "abab" ， n=4 ，可能的 len 为 1 或 2。 步骤 2：计算哈希值 选择哈希函数：简单多项式哈希，例如 \[ hash(s[ 0..k-1]) = \sum_ {i=0}^{k-1} s[ i ] \cdot base^{k-1-i} \] 为方便滚动计算，使用基数 base （如 131）和模数 mod （如 2^64 避免溢出）。 步骤 3：检查重复性 对于每个候选 len ： a. 计算前 len 个字符的哈希值 pattern_hash 。 b. 从索引 len 开始，每次滑动 len 个字符，计算当前子串哈希值： 若使用多项式哈希，滑动时可通过前一个子串的哈希值快速计算新子串哈希值（类似 Rabin-Karp 的滚动哈希）。 c. 若所有子串的哈希值均等于 pattern_hash ，则返回 true 。 步骤 4：边界情况 若 n=1 ，直接返回 false （单个字符无法由子串重复构成，除非重复一次，但题目要求多次重复）。 若没有符合条件的 len ，返回 false 。 示例演示（s = "abab"） n=4 ，候选 len=1 和 len=2 。 先检查 len=2 ： 模式串 "ab" 的哈希值记为 H_ab 。 下一个长度为 2 的子串是 "ab" ，哈希值相同。 所有子串匹配，返回 true 。 复杂度分析 时间复杂度：枚举所有可能的 len （约数个数为 O(√n)），每次检查需 O(n/len) 次操作，总和为 O(n log n)（因约数和函数增长较慢）。 空间复杂度：O(1)（仅存储哈希值）。 关键点 哈希函数需避免碰撞（可通过双哈希增强鲁棒性）。 若不用哈希，直接逐字符比较也可行，但哈希优化在理论上有更优的平均性能。