1. 引言
在本篇文章中，我们将介绍三种判断字符串周期性的方法。换句话说，我们要判断一个字符串是否可以由其某个前缀重复拼接而成。
这在实际开发中有一些应用场景，比如：判断一个模式是否重复出现、字符串压缩、密码学中某些模式识别等。
2. 问题描述
给定一个长度为 n 的字符串 s（n > 1），我们要判断是否存在一个长度为 m 的前缀 z = s[0..m-1]（1 ≤ m < n），使得 s 可以表示为 z 重复拼接若干次的结果。
例如，字符串 abcabcabc 可以由前缀 abc 重复三次构成。
⚠️注意：必须是前缀，例如 bca 不是 abcabcabc 的前缀，所以不能用来构成整个字符串。
3. 暴力解法
思路
遍历所有可能的前缀长度 m（从 1 到 n-1），对每个前缀 z = s[0..m-1]，尝试拼接它若干次是否能还原出 s。
判断方式如下：
- 对于每个位置
i，我们计算它在z中的对应位置(i - 1) % m，然后比较字符是否相等。 - 如果所有位置都匹配，则说明
s是由z构成的。
示例代码（Java）
public class BruteForcePeriodChecker {
public static String checkPeriodicity(String s) {
int n = s.length();
for (int m = 1; m < n; m++) {
String z = s.substring(0, m);
boolean valid = true;
for (int i = 0; i < n; i++) {
if (s.charAt(i) != z.charAt(i % m)) {
valid = false;
break;
}
}
if (valid) return z;
}
return null;
}
}
时间复杂度
- 最坏情况下是 **O(n²)**。
- 因为每个
m都可能需要比较n次字符，总共最多尝试n-1次。
缺点
- 没有提前剪枝，效率低。
- 即使
m不能整除n，也照样尝试，这是不必要的。
4. 优化解法
改进点
- 只尝试那些能整除
n的m值。 - 这样可以减少不必要的尝试。
示例代码（Java）
public class OptimizedPeriodChecker {
public static String checkPeriodicity(String s) {
int n = s.length();
for (int m = 1; m <= n / 2; m++) {
if (n % m != 0) continue;
String z = s.substring(0, m);
boolean valid = true;
for (int i = 0; i < n; i++) {
if (s.charAt(i) != z.charAt(i % m)) {
valid = false;
break;
}
}
if (valid) return z;
}
return null;
}
}
时间复杂度分析
- 最坏情况下，时间复杂度约为 **O(n log n)**。
- 因为只尝试
d(n)个m（即n的因数个数），而d(n)的增长速率远小于n。
优点
- 相比暴力法有明显提升。
- 适用于大多数实际场景。
5. 旋转法（最优解）
核心思想
利用字符串旋转定理：
✅ 一个字符串 s 是其某个子串的重复拼接，当且仅当它是自己的非平凡旋转字符串。
换句话说：
- 如果
s是某个前缀的重复拼接，那么将s拼接两次（s + s）后，s应该出现在s+s的中间某个位置（不是开头或结尾）。
示例说明
s = abcabcabc，拼接后为abcabcabcabcabcabc。- 检查
s是否出现在s+s的中间，即s+s.indexOf(s, 1)是否存在。
示例代码（Java）
public class RotationPeriodChecker {
public static String checkPeriodicity(String s) {
int n = s.length();
String doubled = s + s;
// 查找从位置1开始的 s 出现的位置
int index = doubled.indexOf(s, 1);
if (index != -1 && index < n) {
return s.substring(0, index);
}
return null;
}
}
时间复杂度
- **O(n)**，因为
indexOf在 Java 中使用的是高效的字符串匹配算法（如 KMP 或 Boyer-Moore）。 - 是目前性能最优的解法。
优点
- 线性时间复杂度。
- 实现简洁优雅。
- 是字符串处理中经典的技巧之一。
6. 总结
| 方法 | 时间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(n²) | ✅简单 | 小数据量 |
| 优化法 | O(n log n) | ✅中等 | 中等数据量 |
| 旋转法 | O(n) | ✅中等偏上 | 大数据量、性能敏感场景 |
✅ 推荐优先使用旋转法，它不仅效率高，而且体现了字符串处理中的一个经典思想。
💡踩坑提醒：有些同学会尝试用正则表达式或动态规划来做，但容易写出 bug 或性能不佳的实现。旋转法是更优雅、更稳定的选择。