[LeetCode]day28 459.重复的子字符串

题目链接

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:

输入: s = “aba”
输出: false
示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

解题

方法一：移动匹配

这个方法真的挺难想到的 也有点抽象
原理 如果一个字符串是由相同的子串构成的，当两个相同的字符串组成一个新的字符串时，如果掐头去尾后能在其中查找到原来的字符串，则它是由相同的子串构成的

看图推导一下就知道了

思路总结

• 拼接字符串
• 掐头去尾（因为新的字符串是由原来的两个字符串拼接而成的，如果不进行掐头去尾肯定可以找到原本的字符串）
• 找原本的字符串

代码书写

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        //1.拼接字符串
        string t = s+s;
        //2.掐头去尾
        t.erase(t.begin());
        t.erase(t.end()-1);
        //3.找原本的字符串
        if(t.find(s)!=string::npos) return true;
        return false;
    }
};

方法二： kmp

原理： 找到该字符串的最长相等前后缀，错开的那部分长度如果可以整除字符串长度，那么这个字符串就是由相等的子串组成的

可以通过一下这个图进行理解

思路

• 找到最长相等的前后缀
• 用字符串长度减去最长相等前后缀长度
• 用上述结果整除字符串长度 结果为0 就返回true

代码书写

class Solution {
public:
    void getNext(vector<int>&next,const string&s){
        //1.初始化
        next[0]=0;
        int i=0,j=1;
        for(;j<s.size();j++){
            //2.处理不相同的情况
            while(i>0&&s[i]!=s[j]){
                i=next[i-1];
            }
            //3.处理相同情况
            if(s[i]==s[j]){
                i++;
            }
            //4.更新next数组
            next[j]=i;
        }
        
    }
    bool repeatedSubstringPattern(string s) {
       vector<int>next(s.size());
       getNext(next,s);
       for(int i=0;i<next.size();i++){
        cout<<next[i];
       }
       //求子串长度
       int sub= s.size()-next[s.size()-1];
       if(next[s.size()-1]!=0&&s.size()%sub==0) return true;
       return false;
    }
};