重复模式匹配问题

题目描述：给定一个字符串 s 和一个模式 p，判断 s 中是否存在 p 的重复模式。具体来说，p 的重复模式是指将 p 重复多次后形成的字符串。例如，如果 p = "ab"，那么 "ababab" 就是 p 的重复模式。

解题过程：

1. 问题分析：

   • 我们需要判断字符串 s 是否由模式 p 重复多次构成
   • 关键是要找到 s 的长度与 p 的长度之间的关系
   • 如果 s 是 p 的重复模式，那么 s 的长度必须是 p 的长度的整数倍

2. 基础思路：

   • 首先检查 s 的长度是否能被 p 的长度整除
   • 如果不能整除，那么 s 肯定不是 p 的重复模式
   • 如果能够整除，计算重复次数 k = len(s) / len(p)

3. 哈希算法应用：

   • 使用滚动哈希来计算字符串的哈希值
   • 为模式 p 计算一个基准哈希值
   • 将 s 分割成 k 个长度为 len(p) 的子串
   • 检查每个子串的哈希值是否与 p 的哈希值匹配

4. 具体实现步骤：

   • 定义哈希函数，使用多项式滚动哈希
   • 计算模式 p 的哈希值 hash_p
   • 遍历 s，计算每个长度为 len(p) 的子串的哈希值
   • 比较每个子串的哈希值与 hash_p 是否相等

5. 哈希冲突处理：

   • 使用双重哈希来减少哈希冲突的可能性
   • 或者在实际比较哈希值相等时，再进行一次字符串的逐字符比较

6. 优化考虑：

   • 如果字符串很长，可以提前发现不匹配的情况
   • 使用模运算来避免整数溢出
   • 选择合适的基数（通常选择质数）来减少冲突

7. 边界情况处理：

   • 空字符串的处理
   • s 长度小于 p 长度的情况
   • p 为空字符串的情况

这个算法的时间复杂度是 O(n)，其中 n 是字符串 s 的长度，因为只需要遍历一次字符串。空间复杂度是 O(1)，只需要常数级别的额外空间。