每日leetcode

459. 重复的子字符串 - 力扣（LeetCode）

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

思路

1. 只想到了暴力的方法orz，每次匹配串增加一个字符，然后逐个进行比较。

代码实现

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = 1, n = s.length(), times;
        bool flag;
        string tem = "";
        tem += s[0];
        if(n == 1) return false;
        while(len <= n/2) {
            if(n % len != 0) continue;
            times = n / len;
            flag = true;
            int i = len;
            while(i < n) {
                int j = 0;
                while(j < len) {
                    if(s[i] != tem[j]) {
                        flag = false;
                        break;
                    }
                    ++i;
                    ++j;
                }
                if(!flag) break;
            }
            if(flag) return true;
            tem += s[len++];
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n)。

官方题解

• 我那种实现空间复杂度其实可以降到O(1)，因为取的就是字符串的前缀串，所以不用另外开辟一个空间存，保存一个活动指针即可。

• class Solution {
  public:
      bool repeatedSubstringPattern(string s) {
          int len = 1, n = s.length();
          bool flag;
          if(n == 1) return false;
          while(len <= n/2) {
              if(n % len != 0) {
                  ++len;
                  continue;
              }
              flag = true;
              int i = len;
              while(i < n) {
                  int j = 0;
                  while(j < len) {
                      if(s[i] != s[j]) {
                          flag = false;
                          break;
                      }
                      ++i;
                      ++j;
                  }
                  if(!flag) break;
              }
              if(flag) return true;
              ++len;
          }
          return false;
      }
  };

• len也可以省，直接用i来指导即可。(到这一步基本暴力算法的多余计算都处理掉了)

• class Solution {
  public:
      bool repeatedSubstringPattern(string s) {
          int n = s.length();
          for(int i = 1; i <= n/2; ++i) {
              if(n % i == 0) {
                  bool flag = true;
                  for(int j = i; j < n; j++) {
                      if(s[j] != s[j-i]) {
                          flag = false;
                          break;
                      }
                  }
                  if(flag) return true;
              }
          }
          return false;
      }
  };

• 文中有种双倍串判断的方法，就是本身加本身，如果新的字符串掐头去尾后原字符串是剩下字符串的子串的话，那么这个字符串就是一个周期串。——理由感觉可以这样理解，假设原字符串长度为n，双倍串的长度为2n，那么如果掐头去尾后找到一个原字符串作为子串，那么从0到该子串所在的开始位置就发生一次回正，因为新串是掐头去尾长度为n-2，而子串仍为n，那么子串必然是跨过两个拼接字符串的，设子串的其实位置是i，那么过了n位后的起始位置是原字符串的第n-i位，相当于该字符串向后移动了n-i位仍然匹配，那么因为a[0]=a[n-i]=a[n-i+n-i]=...所以这个就是该字符串的重复串了，也就是说，如果我们能找到这个子串的话，那么他到第一串尾的长度就是重复串的长度。——所以我们就可以令s+s再从1到2n-2的范围内搜索子串，若存在即有重复串。
• 另一种方法又是KMP算法（我以为这个方法只能找第一个匹配串的下标呢），仔细想想好像确实是这样呢。
• 这个思路是上一方法的优化版本，从上一思路中我们知道如果其中部分字符串向后移动后还能匹配，设移动了i位，那么a[0]=a[i]=a[i+i]=...，相对地，a[n-1]=a[n-i-1]=a[n-1-2i]，可以想一想，假设相同串重叠的位置为块2，前面的位置为块1，后面的位置为块3，那么重叠部分和块1相同的部分为块2-1，那么以此类推，因为块2-1和块1匹配，而块2-1往后挪块1那么大的位置又和块2-1匹配，只要这个比例能够一直保持，那么就能完全覆盖，找到最长前后缀串后需要判断中间重叠的部分是否能整除块1的规模（换言之，字符串是否能整除块1）。
• 那么事情就清晰了，其实我们就是需要找一个和某一前缀匹配的后缀串即可，那么就可以转化为KMP算法求最长相同前缀后缀串再判断多余部分是否能被整除即可。
• 时间复杂度：因为只有求前后缀串，不用找位置，所以时间开销是O(n)的。
• 空间复杂度：move数组——O(n)。
• 复现：

• class Solution {
  public:
      bool repeatedSubstringPattern(string s) {
          int n = s.length();
          vector<int> move(n, 0);
          for(int i = 1, j = 0; i < n; ++i) {
              while(j > 0 && s[i] != s[j]) {
                  j = move[j-1];
              }
              if(s[i] == s[j]) ++j;
              move[i] = j;
          }
          return move[n-1] != 0 && n % (n-move[n-1]) == 0;
      }
  };