题目：给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1：
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2：
输入: s = "aba"
输出: false
示例 3：
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
- 1 <= s.length <= $10^4$
- s 由小写英文字母组成
题目来源：力扣（LeetCode）链接
题解：
- 方法一：移动匹配
字符串abcabc
class Solution {
public boolean repeatedSubstringPattern(String s) {
// 拼接 s+s，去除 s+s 的首字母和尾字符
String t = (s + s).substring(1, 2 * s.length() - 1);
// 如果新字符串里面还有一个 s，则说明 s 是由重复字符串组成的
return t.contains(s);
}
}
- 方法二：KMP 算法
在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串
- 举例说明
- 举例说明
class Solution {
public boolean repeatedSubstringPattern(String s) {
// 如果为 ""，直接返回 false
if (s.equals("")) {
return false;
}
int len = s.length;
// 求出字符串 s 的前缀表
int[] next = new int[len];
int j = 0;
next[0] = j;
for (int i = 0; i < len; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = next[j];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
next[i] = j;
}
// 如果最长相同前后缀不为 0，且字符串长度是最长相等前后缀不包含的子串长度的倍数
// 就说明字符串是由最长相等前后缀不包含的子串重复组成的
if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0) {
return true;
}
return false;
}
}