Leetcode459重复的子字符串

问题描述

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

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

2. 示例 2:
  - 输入: s = "aba"
  - 输出: false

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

提示：

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

解法一：暴力(BruteForce)

我们可以使用两层for循环来暴力解决这个问题，思路较为简单。

1. 考虑到一定是从索引0开始的子串，所以我们子串的长度从1、2、3一直尝试。
2. 每次我们利用cpp中的函数substr来取子串，和主串中的元素相比较，因为我们取了前length个字符，所以我们可以直接跳过这部分的比较。
3. 最后再进行简单的逻辑判断即可。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();

        for(int length = 1; length <= n / 2; length++){
            bool match = true;
            string pattern = s.substr(0,length);

            for(int i = length; i < n; i += length){
                if(pattern != s.substr(i, length)){
                    match = false;
                    break;
                }
            }

            if(match) return true;
        }

        return false;
    }
};

解法二：巧妙的设计：移动匹配

这是一种十分巧妙的算法，假设我们的要判断的文本串为s，则我们可以将两个s拼接起来，然后为了避免重复，我们“掐头去尾”，即去掉第一个字符和最后一个字符，在剩下的字符串中查看是否出现了子串即可。

代码如下：

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

代码学习笔记：

1. 要熟练掌握cpp中string类的find()和erase()方法，find()方法返回索引，erase()方法用来删除某个字符。
2. 注意迭代器的begin()指向第一个元素，而end()不是指向最后一个元素，而是最后一个元素的下一个空位置。
3. npos是std::string中的一个静态成员常量，数据类型为size_t，其经常用来表示在字符串查找函数中没有找到，值为64位无符号数的最大值，我们可以调用打印来尝试一下。

#include <iostream>
#include <string>
int main(){
  std::cout<<std::string::npos<<std::endl;
  //输出结果为18446744073709551615，二进制也就是64个1
  return 0;
}