459. 重复的子字符串【力扣】——kmp拼接字符串解法

常规kmp解答

class Solution {
public:void getNext(int *next,string s){int j=0;next[0]=0;for(int i=1;i<s.size();i++){while(j>0 && s[i]!=s[j]){j=next[j-1];}if(s[i]==s[j]) j++;next[i]=j;}}bool repeatedSubstringPattern(string s) {if(s.size()==0) return false;int next[s.size()];getNext(next,s);if(next[s.size()-1]!=0 && s.size()%(s.size()-next[s.size()-1])==0){return true;}return false;}// 若 s="abcabcabc"，则next[]=[0,0,0,1,2,3,4,5,6]// next数组记录的时相同字符串的长度
};

拼接字符串解法

我看评论区一个大佬的理解___大佬链接
大佬的思路：

解题过程
1、如果一个字符串当中有重复的子串，那么把这个字符串拼接，并且去掉头字符和尾字符，这个拼接的字符串肯定包含原字符串；如果不包含则不含有重复的子字符串
2、技巧：拼接原始字符串，去掉头字符，查找原始字符串，如果返回的位置不是拼接的位置，就含有重复的子字符串----拼接位置即匹配结束

简单题，一般不会让手写KMP算法，但是调用API，底层用的是KMP算法，因此时间复杂度和空间复杂度都是O(N)

class Solution {
public:bool repeatedSubstringPattern(string s) {// 时间复杂度O(N)，空间复杂度O(N)return (s + s).find(s, 1) != s.size();}
};

大佬链接
459. 重复的子字符串【力扣】