每日一题(LeetCode)----字符串--重复的子字符串
每日一题(LeetCode)----字符串–重复的子字符串
1.题目（459. 重复的子字符串）
-
给定一个非空的字符串
s，检查是否可以通过由它的一个子串重复多次构成。示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。示例 2:
输入: s = "aba" 输出: false示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)提示：
1 <= s.length <= 104s由小写英文字母组成
2.解题思路
思路一：
判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
另外我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
作者：代码随想录
链接：代码随想录 (programmercarl.com)
2.创建两个指针来对要进行反转的地方进行反转
思路二：使用了KMP
通过分析：如果数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串，所以我们先用KMP求出Next数组，然后用分析出来的公式进行判断
思路来源：代码随想录
链接：代码随想录 (programmercarl.com)
3.写出代码
思路一的代码
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t=s+s;
t.erase(t.begin());
t.erase(t.end()-1);
if(t.find(s)!=std::string::npos){
return true;
}
return false;
}
};
作者：代码随想录
链接：代码随想录 (programmercarl.com)
思路二的代码
class Solution {
public:
void getNext(int* next ,string s){
int len=s.size();
next[0]=0;
int i=0;
for(int j=1;j<len;j++){
while(i>0&&s[i]!=s[j]){
i=next[i-1];
}
if(s[i]==s[j]){
i++;
}
next[j]=i;
}
}
bool repeatedSubstringPattern(string s) {
int length=s.size();
if(length==0){
return false;
}
int next[length];
getNext(next,s);
if(next[length-1]!=0&&length%(length-(next[length-1]))==0){
return true;
}
return false;
}
};