题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 1 <= s.length <= 10^4

  • s 由小写英文字母组成

    解题方法

    优化的KMP

    对于题目中描述的字符串s，假设其重复子串为t，则s.size() % t.size() == 0，并且对s求出的next数组满足[0,..,0,1,2,3,...]的形式，并且其中0的个数即t.size()，此时只要s.size() % (s.size()-next(s.size()-1)) == 0，则s包含重复子串。
    该方法时间复杂度为O(n)，空间复杂度O(n)
    c++代码

    class Solution {
public:
  vector<int> getNext(string s) {
      vector<int> next;
      int i = 0;
      int j = 1;
      int n = s.size();
      next.push_back(i);

      while(j<n) {
          if(s[i]==s[j]) {
              i++;
              next.push_back(i);
              j++;
          }
          else {
              if(i>0) {
                  i = next[i-1];
              }
              else {
                  next.push_back(i);
                  j++;
              }
          }
      }

      return next;
  }

  bool repeatedSubstringPattern(string s) {
      int n = s.size();
      vector<int> next = getNext(s);

      if(next[n - 1] != 0 && n%(n-next[n-1])==0) return true;
      else return false;
  }
};