重復的子字符串

給定一個非空的字符串 s ，檢查是否可以通過由它的一個子串重復多次構(gòu)成。

示例 1:

輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復兩次構(gòu)成。

示例 2:

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

示例 3:

輸入: s = "abcabcabcabc"
輸出: true
解釋: 可由子串 "abc" 重復四次構(gòu)成。 (或子串 "abcabc" 重復兩次構(gòu)成。)

方法一：枚舉
如果一個長度為 n 的字符串 s 可以由它的一個長度為 n′ 的子串 s′重復多次構(gòu)成，那么：

• n 一定是 n' 的倍數(shù)；
• s′ 一定是 s 的前綴；
• 對于任意的 i∈[n′,n)，有 s[i]=s[i?n′]

也就是說，s 中長度為 n′ 的前綴就是 s′，并且在這之后的每一個位置上的字符 s[i]，都需要與它之前的第 n′ 個字符 s[i?n′]相同。
因此，我們可以從小到大枚舉 n' ，并對字符串 s 進行遍歷，進行上述的判斷。注意到一個小優(yōu)化是，因為子串至少需要重復一次，所以 n′ 不會大于 n 的一半，我們只需要在 [1,n/2] 的范圍內(nèi)枚舉 n′ 即可。

public boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    // i表示n'字符串的長度
    for (int i = 1; i * 2 <= n; i++) {
        if (n % i != 0) {
            continue;
        }
        boolean match = true;
        for (int j = i; j < n; j++) {
            if (s.charAt(j) != s.charAt(j - i)) {
                match = false;
                break;
            }
        }
        if (match) {
            return true;
        }
    }
    return false;
}

時間復雜度：O(n²)

方法二：字符串匹配
我們可以把字符串 s寫成s′s′?s′s′s's' 的形式，總計 n/n′個 s′。但我們?nèi)绾卧诓幻杜e n′ 的情況下，判斷 s 是否能寫成上述的形式呢？

如果我們移除字符串 s 的前 n′ 個字符（即一個完整的 s′），再將這些字符保持順序添加到剩余字符串的末尾，那么得到的字符串仍然是 s。由于 1≤n′<n，那么如果將兩個 s 連在一起，并移除第一個和最后一個字符，那么得到的字符串一定包含 s，即 s 是它的一個子串。

因此我們可以考慮這種方法：我們將兩個 s 連在一起，并移除第一個和最后一個字符。如果 s 是該字符串的子串，那么 s就滿足題目要求。

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

方法三：KMP