重复模式匹配问题

题目描述
给定一个字符串 s，检查它是否可以由它的一个子串重复多次构成。例如，输入 "abab" 应该返回 true，因为它可以由 "ab" 重复两次构成；输入 "abc" 应该返回 false，因为它不能由任何子串重复构成。

解题过程

1. 问题分析
   我们需要判断字符串 s 是否能被其某个真子串（长度小于 s）重复多次构成。关键观察点是：如果 s 可以由长度为 k 的子串重复构成，那么：

   • s 的长度必须是 k 的倍数
   • 对于所有 i，s[i] 应该等于 s[i % k]

2. 暴力解法思路
   最直接的方法是枚举所有可能的子串长度 k（1 ≤ k ≤ n/2，其中 n 是 s 的长度），检查是否满足条件：

   • 如果 n 不能被 k 整除，跳过
   • 检查 s 是否等于前 k 个字符重复 n/k 次

3. 哈希算法优化
   我们可以使用滚动哈希来优化比较过程：

   • 计算整个字符串的哈希值
   • 对于每个可能的 k，计算前 k 个字符的哈希值
   • 通过滚动哈希计算预期重复串的哈希值，与实际哈希值比较

4. 具体实现步骤
   以多项式哈希为例：

   • 选择基数 base 和模数 mod
   • 预处理字符串的哈希前缀和 base 的幂次
   • 对于每个可能的 k：
     • 计算子串 s[0:k] 的哈希值 h1
     • 通过滚动哈希计算重复 n/k 次后的理论哈希值
     • 比较理论哈希值与实际哈希值

5. 双倍字符串技巧
   更巧妙的方法：将两个 s 连接在一起形成 ss = s + s，然后去掉首尾字符得到 ss[1:-1]。如果 s 是重复的，那么 ss[1:-1] 中必定包含完整的 s。

6. KMP算法应用
   使用KMP算法计算next数组：

   • 如果 n % (n - next[n-1]) == 0 且 next[n-1] ≠ 0
   • 那么最小重复单元长度为 n - next[n-1]

示例演示
以 s = "abab" 为例：

• 长度 n = 4
• 可能 k = 1, 2（因为 k ≤ n/2）
• 当 k = 2 时：n/k = 2，前2个字符 "ab" 重复2次得到 "abab"，匹配成功

这种方法的时间复杂度从暴力解法的 O(n²) 优化到 O(n)，适合处理大规模字符串。