459. 重复的子字符串

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

示例 1:

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

示例 2:

输入: s = "aba"
输出: false

示例 3:

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

提示：

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

对称

字符串加倍，破坏首尾字符串，检查剩余字符串是否包含原字符串。

假设字符串s是由s1+s2组成的，s+s后，str就变成了s1+s2+s1+s2，去掉首尾，破坏了首尾的s1和s2， 变成了s3+s2+s1+s4,此时str中间就是s2+s1,如果s是循环字串，也就是s1=s2,所以str中间的s2+s1就和原字符串相等。 如果s不是循环字串，s1!=s2，那么s1+s2是不等于s2+s1的，也就是str中间不包含s。

class Solution {
   public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
   }
}

时间复杂度分析：

1. 拼接操作 (s + s)：
   • 需要复制 s 的内容到新字符串 str 中，时间复杂度是 O(n)。
2. substring(1, str.length() - 1)：
   • 这个操作创建了一个新的子字符串，长度为 2n - 2，需要复制这部分的内容到新的字符串对象。时间复杂度为 O(n)。
3. contains(s)：
   • 在长度为 2n - 2 的新字符串中查找原字符串 s。其时间复杂度为 O(n)，假设是通过 KMP 或 Rabin-Karp 等高效算法实现的。

综合起来，总的时间复杂度为 O(n)，因为每步操作的时间复杂度都是线性的。

空间复杂度分析：

1. 拼接操作 (s + s)：
   • 创建了一个新字符串 str，占用了 2n 的空间。
2. substring(1, str.length() - 1)：
   • substring() 方法会创建一个新的字符串，长度为 2n - 2，占用了额外的 O(n) 空间。
3. contains(s)：
   • contains 操作不会创建额外的大量空间，只是一些内部变量可能会使用常量级别的空间，因此这里不增加空间复杂度。

因此，总的空间复杂度为 O(2n - 2)，即 O(n)。

双重遍历

类似28. 找出字符串中第一个匹配项的下标。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 获取字符串的长度
        int n = s.length();
        
        // 遍历可能的子串长度，从 1 到 n 的一半。重点。注意i是长度，所以要从1开始。
        for (int i = 1; i * 2 <= n; ++i) {
            // 如果 n 是 i 的倍数，才可能构成重复子串。重点
            if (n % i == 0) {
                // 初始化一个标志位，表示当前子串是否匹配
                boolean match = true;
                
                // 遍历字符串，检查每个字符是否与子串的相应字符相同。
                // 注意第一个for遍历的是长度，第二个for遍历的是索引，从i开始，
                // 因为[0,i-1]有i个字符。比较[0,i-1]和[i,2i-1]的每个对应位置的元素，
                // 即i和0，……，2i-1和i-1，然后比较[i,2i-1]和[2i,3i-1]的每个对应位置的元素，直到把[i+1,n]中的元素都比较完。重点
                for (int j = i; j < n; ++j) {
                    // 如果有任意一个字符不匹配，设置标志位为 false 并退出内层循环
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                
                // 如果标志位为 true，表示字符串可以由该子串重复构成，返回 true
                if (match) {
                    return true;
                }
            }
        }
        
        // 如果遍历完成后没有找到重复的子串，返回 false
        return false;
    }
}

• 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。枚举 i 的时间复杂度为 O(n)，遍历 s 的时间复杂度为 O(n)，相乘即为总时间复杂度。
• 空间复杂度：O(1)。