重复的子字符串

459. 重复的子字符串

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

示例 1:

输入: "abab"

输出: True

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

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

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

方法一：枚举

如果一个长度为 n 的字符串可以由它的一个长度为 n‘ 的子串 s’ 重复多次构成，那么：

• n 一定是 n‘ 的倍数；
• s’ 一定是 s 的前缀；
• 对于任意的 i∈[n', n)，有 s[i] = s[i - n']。

我们枚举子串的长度 n’ ，同时判断 s[i] 和 s[i - n’] 是否相等。子串的长度 n’ 属于 [1, n / 2]，长度为 n 的字符串至少要由两个重复子串构成。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for(int i = 1; i <= n / 2; i++){
            //字符串长度不能整除子串的长度，continue
            if(n % i != 0){
                continue;
            }
		
            boolean flag = true;
            //判断子串s[0 ... i - 1] 是否为重复的子串
            for(int j = i; j < n; j++){
                if(s.charAt(j) != s.charAt(j - i)){
                    flag = false;
                    break;
                }
            }
            
            if(flag){
                return true;
            }
        }
        return false;
    }
}

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