字符串——459. 重复的子字符串
1 题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
2 题目示例
示例 1: 输入: s = “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。
示例 2: 输入: s = “aba” 输出: false
示例 3: 输入: s = “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
3 题目提示
1 <= s.length <= 104 s 由小写英文字母组成
4 思路
方法一：字符串匹配 我们可以把字符串 ss 写成s’s’···s’s’的形式。
如果我们移除字符串s的前n’个字符（即一个完整的s’)，再将这些字符保持顺序添加到剩余字符串的末尾，那么得到的字符串仍然是s。由于1 ≤ n’≤ n，那么如果将两个s连在一起，并移除第一个和最后一个字符，那么得到的字符串—定包含s，即s是它的一个子串。 因此我们可以考虑这种方法:我们将两个s连在一起，并移除第一个和最后一个字符。如果s是该字符串的子串，那么s就满足题目要求。 证明需要使用一些同余运算的小技巧，可以见方法三之后的「正确性证明」部分。这里先假设我们已经完成了证明，这样就可以使用非常简短的代码完成本题。在下面的代码中，我们可以从位置 11 开始查询，并希望查询结果不为位置 nn，这与移除字符串的第一个和最后一个字符是等价的。
复杂度分析
由于我们使用了语言自带的字符串查找函数，因此这里不深入分析其时空复杂度。
方法二：：KMP 算法 由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。
5 我的答案
class Solution {
public boolean repeatedSubstringPattern(String s) {
return (s + s).indexOf(s, 1) != s.length();
}
}class Solution {
public boolean repeatedSubstringPattern(String s) {
return kmp(s + s, s);
}
public boolean kmp(String query, String pattern) {
int n = query.length();
int m = pattern.length();
int[] fail = new int[m];
Arrays.fill(fail, -1);
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
fail[i] = j + 1;
}
}
int match = -1;
for (int i = 1; i < n - 1; ++i) {
while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
match = fail[match];
}
if (pattern.charAt(match + 1) == query.charAt(i)) {
++match;
if (match == m - 1) {
return true;
}
}
}
return false;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
