重復的子字符串
給定一個非空的字符串 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(n2)
方法二：字符串匹配
我們可以把字符串 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
