每日一题(LeetCode)----字符串--重复的子字符串

每日一题(LeetCode)----字符串–重复的子字符串

1.题目（459. 重复的子字符串）

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

  示例 1:

  输入: s = "abab"
  输出: true
  解释: 可由子串 "ab" 重复两次构成。
  

  示例 2:

  输入: s = "aba"
  输出: false
  

  示例 3:

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

  提示：

  • 1 <= s.length <= 104
  • s 由小写英文字母组成

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;
    }
};

思路来源：代码随想录

链接：代码随想录 (programmercarl.com)