题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

样例

输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

输入: "aba"
输出: False

算法1

(模拟) $O(n^2)$

C++ 代码

class Solution {
public:
    bool help(const string& str, const string& subs){
        int start=0, len=subs.size();
        while(start<str.size()){
            if(str.substr(start,len)!=subs)return false;
            start+=len;
        }
        return true;
    }
    bool repeatedSubstringPattern(string s) {
        if(s.empty()||s.size()==1)return false;
        int sz=s.size();
        int len=1;
        while(len<sz){
            if(sz%len==0){
                if(help(s,s.substr(0,len)))return true;
            }
            len++;
        }
        return false;
    }
};

算法2

(emmm急转弯)

C++ 代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s+s).find(s, 1)!=s.size();
    }
};

算法3

(KMP)

这里就不写了，见 leetcode 214. 最短回文串