重复模式匹配问题

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

解题过程：

1. 问题分析
   我们需要判断字符串 s 是否由某个子串 pattern 重复多次构成。这意味着：

• s 的长度必须是 pattern 长度的整数倍
• s 应该等于 pattern 重复 n 次的结果

2. 关键观察
   如果 s 可以由子串 pattern 重复构成，那么将两个 s 连接起来形成 s + s，然后去掉首尾字符，原字符串 s 应该仍然出现在这个新字符串中。

例如 s = "abab"：

• s + s = "abababab"
• 去掉首尾字符："bababa"
• 在这个字符串中查找 s："abab" 确实出现在 "bababa" 中

3. 算法步骤
   步骤1：检查边界情况

• 如果字符串长度为0或1，直接返回false

步骤2：构造新字符串

• 创建新字符串 str = s + s
• 去掉str的首尾字符，得到 str = str.substring(1, str.length() - 1)

步骤3：检查包含关系

• 判断 str 中是否包含原字符串 s
• 如果包含，返回true；否则返回false

4. 正确性证明
   如果 s 由 pattern 重复 n 次构成（n ≥ 2）：

• s + s 将由 pattern 重复 2n 次构成
• 去掉首尾字符后，中间部分仍然包含完整的 s
  如果 s 不能由子串重复构成：
• 去掉首尾字符后的字符串将不包含完整的 s

5. 复杂度分析

• 时间复杂度：O(n)，其中n是字符串长度
• 空间复杂度：O(n)，需要存储连接后的字符串

6. 示例验证
   例1：s = "abab"

• s + s = "abababab"
• 去掉首尾："bababa"
• "bababa" 包含 "abab" → 返回true

例2：s = "abc"

• s + s = "abcabc"
• 去掉首尾："bcab"
• "bcab" 不包含 "abc" → 返回false

这种方法巧妙地利用了字符串的周期性特征，通过简单的字符串操作就能高效解决问题。