459.重复的子字符串

题目来源:https://leetcode-cn.com/problems/repeated-substring-pattern/

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

示例1:

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

示例2:

输入: “aba”

输出: False

示例3:

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

解法

C++代码:

解法一:暴力穷举法

根据题目的要求,可以得到的结论有:

1.子字符串一定从给定字符串开头开始,且子字符串的长度是整个字符串长度的因子;

2.将字符串按照子字符串的长度进行分组,如果给定字符串可由该子字符串重复构成,则每个分组的对应位字符相同。

由上述的结论,可以枚举整个字符串以判断是否存在满足条件的子串,代码如下:

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length(),i,j,k;
        for(i=1; i<=len/2; i++)
        {
            if(len % i == 0){  // 能够整除子串长度
                for(j=0; j<i; j++) {
                    for(k=j+i; k<len; k=k+i){
                        if(s[j]!=s[k])
                            break;
                    }
                    if(k<len)
                        break;
                }
                if(j>=i)
                    return true;
            }
        }
        return false;
    }
};

时间复杂度:O(n^3)

空间复杂度:O(1)

解法二:双倍字符串

假设字符串s没有循环节,则在s+s串中从第二个字符开始寻找s,则找到的位置为s.length();但是若字符串s有循环节,则在s+s串中从第二个字符开始寻找s,则找到的位置必然是s中第二个循环节的起始位置,而不是字符串末尾,证明略。代码如下:

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

时间复杂度:依赖于字符串自带的find函数的时间复杂度

空间复杂度:O(n) // 字符串长度扩展了一倍