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. 重复的子字符串【力扣】

原文地址：https://blog.csdn.net/XiaoBino_O/article/details/145113387

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！