459. 重复的字符串

题目

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

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

示例 2:
输入: "aba"
输出: False

示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

方法1

一个字符串若可以由它的子串重复多次构成，那么这个子串的长度只可能为1、2、3、…n/2，且字符串s的长度必须要是子串长度的倍数。我们只要分别进行如下判断即可：

• 长度为1的子串能否重复多次构成字符串s
• 长度为2的子串能否重复多次构成字符串s
• 长度为3的子串能否重复多次构成字符串s
• …….
• 长度为$n/2$的子串能否重复多次构成字符串s

对于以上每种可能的情况，我们都需要遍历整个字符串，检查是否满足重复条件$s[j] == s[j - i]$ (其中，i为子串长度)。只要以上情况有一种满足，即可返回true。

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    //i为可能的重复子串长度
    for(int i = 1; i <= n/2; i++){
        //字符串长度必须要是子串长度的倍数
        if(n % i == 0){
            //flag用来记录长度为i的子串能否重复构成字符串
            boolean flag = true;
            for(int j = i; j < n; j++){
                if(s.charAt(j) != s.charAt(j - i))
                    flag = false;
            }
            if(flag)
                return true;
        }
        return false;
    }
}

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

方法2

将两个s拼接到一起形成$s’$,然后在$s’$中寻找s（易知：如果某一重复子串能构成s，那么肯定也能构成$s’$）

• 如果s不能由一子串重复构成，如”aba”,那么$s’$中只有两个s，在$s’:“abaaba”$中查找s，第一个出现s的位置必然是s的长度n
• 如果s能由一子串重复构成，如”abab”,那么$s’$中将不只有两个s（此例子中有3个），在$s’:“abababab”$中查找s，第一个出现s的位置肯定不是s的长度n

public boolean repeatedSubstringPattern(String s) {
    return (s + s).indexOf(s, 1) != s.length();
}