🌸題目
🍁給定一個非空的字元串，判斷它是否可以由它的一個子串重複多次構成。給定的字元串隻含有小寫英文字母，并且長度不超過10000。
示例 1:
輸入: "abab"
輸出: True
解釋: 可由子字元串 "ab" 重複兩次構成。
示例 2:
輸入: "aba"
輸出: False
示例 3:
輸入: "abcabcabcabc"
輸出: True
解釋: 可由子字元串 "abc" 重複四次構成。 (或者子字元串 "abcabc" 重複兩次構成。)
🌸分析
暴力出奇迹，優化見真章！
🌸解法一：暴力解法（直接比對）
private static boolean repeatedSubstringPattern1(String s) {
if(s.length() == 0||s.length()==1) return false;
List<Integer> indexes =new ArrayList<>();
indexes.add(0);
//計算出所有有可能的子串長度
for (int i = 1; i <s.length() ; i++) {
//和第0個位置的字元相等，且總字元串的長度能夠整除目前子串長度
if(s.charAt(i)==s.charAt(0)
&&s.length()%i==0){
indexes.add(i);
}
}
for (int i = 1; i < indexes.size() ; i++) {
int length =indexes.get(i); //目前考慮的子串長度機關
String str = s.substring(0,length); //子串
int j = length;
//以目前考慮的長度機關進行周遊，如果每隔length的子串都等于str，
//并且周遊到了字元串末尾，說明結果為true，反之跳出考慮下一種子串長度
for (; j <s.length() ; j=j+length) {
if(!s.substring(j,j+length).equals(str))
break;
}
if(j==s.length())
return true;
}
return false;
}
🌸解法二： 暴力解法（枚舉）
如果一個長度為n的字元串s可以由它的一個長度為
n'
的子串
s'
重複多次構
成，那麼:
- n—定是
n'
-
s'
- 對于任意的
i ∈[n’, 7)
s[2]= s[i - n']
也就是說，s中長度為
n'
的字首就是
s'
，并且在這之後的每一個位置上的字元
s[i]
，都需要與它之前的第
n'
個字元
s[i-n'
]相同。
是以，我們可以從小到大枚舉
n'
，并對字元串s進行周遊，進行上述的判斷。注
意到一個小優化是，因為子串至少需要重複一次，是以
n'
不會大于n的一半，我
們隻需要在
[1, n/2]
的範圍内枚舉
n'
即可。
private static boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int i = 1; i * 2 <= n; ++i) {
if (n % i == 0) {
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;
}
🌸解法三：移動比對
如果您的字元串S包含一個重複的子字元串，那麼這意味着您可以多次“移位和換行"您的字元串，并使其與原始字元串比對。
例如:abcabc
- 移位一次:cabcab
- 移位兩次:bcabca
- 移位三次:abcabc
現在字元串和原字元串比對了，是以可以得出結論存在重複的子串
基于這個思想，可以每次移動k個字元，直到比對移動length -1次。但是這樣對于重複字元串很長的字元串，效率會非常低。在LeetCode中執行時間逾時了。
為了避免這種無用的環繞，可以建立一個新的字元串str;它等于原來的字元串S再加上S自身，這樣其實就包含了所有移動的字元串。
比如字元串: S= acd，那麼str = S+S = acdacd
acd移動的可能: dac、cda。其實都包含在了str中了。就像一個滑動視窗一開始acd (acd)，移動一次ac(dac)d,移動兩次a(cda)cd。循環結束
是以可以直接判斷str中去除首尾元素之後，是否包含自身元素。如果包含。則表明存在重複子串。
private static boolean repeatedSubstringPattern2(String s) {
String str = s + s;
return str.substring(1, str.length() - 1).contains(s);
}
🌸解法四：KMP（留下了無知的淚水，太難了。）
讀者需要注意以下幾點:
- KMP 算法雖然有着良好的理論時間複雜度上限，但大部分語言自帶的字元串查找函數并不是用 KMP 算法實作的。這是因為在實作 API 時，我們需要在平均時間複雜度和最壞時間複雜度二者之間權衡。普通的暴力比對算法以及優化的 BM 算法擁有比 KMP 算法更為優秀的平均時間複雜度；
- 學習 KMP 算法時，一定要了解其本質。如果放棄閱讀晦澀難懂的材料（即使大部分講解 KMP 算法的材料都包含大量的圖，但圖畢竟隻能描述特殊而非一般情況）而是直接去閱讀代碼，是永遠無法學會 KMP 算法的。讀者甚至無法了解 KMP 算法關鍵代碼中的任意一行。
由于本題就是在一個字元串中查詢另一個字元串是否出現，可以直接套用 KMP 算法。是以這裡對 KMP 算法本身不再贅述。讀者可以自行查閱資料進行學習。這裡留了三個思考題，讀者可以在學習完畢後嘗試回答這三個問題，檢驗自己的學習成果：
- 設查詢串的的長度為 n，模式串的長度為 m，我們需要判斷模式串是否為查詢串的子串。那麼使用 KMP 算法處理該問題時的時間複雜度是多少？在分析時間複雜度時使用了哪一種分析方法？
- 如果有多個查詢串，平均長度為 n，數量為 k，那麼總時間複雜度是多少？
- 在 KMP 算法中，對于模式串，我們需要預處理出一個fail 數組（有時也稱為 next 數組、π 數組等）。這個數組到底表示了什麼？
public boolean repeatedSubstringPattern3(String s) {
return kmp(s + s, s);
}
public boolean kmp(String query, String pattern) {
int n = query.length();
int m = pattern.length();
int[] fail = new int[m];
Arrays.fill(fail, -1);
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
fail[i] = j + 1;
}
}
int match = -1;
for (int i = 1; i < n - 1; ++i) {
while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
match = fail[match];
}
if (pattern.charAt(match + 1) == query.charAt(i)) {
++match;
if (match == m - 1) {
return true;
}
}
}
return false;
}
🌸正确性證明
題解出自@LeetCode-Solution
🌸思考題答案
- 設查詢串的的長度為 n，模式串的長度為 m，我們需要判斷模式串是否為查詢串的子串。那麼使用 KMP 算法處理該問題時的時間複雜度是多少？在分析時間複雜度時使用了哪一種分析方法？
- 時間複雜度為 O(n+m)，用到了均攤分析（攤還分析）的方法。
- 具體地，無論在預處理過程還是查詢過程中，雖然比對失敗時，指針會不斷地根據 fail 數組向左回退，看似時間複雜度會很高。但考慮比對成功時，指針會向右移動一個位置，這一部分對應的時間複雜度為 O(n+m)。又因為向左移動的次數不會超過向右移動的次數，是以總時間複雜度仍然為 O(n+m)。
- 如果有多個查詢串，平均長度為 n，數量為 k，那麼總時間複雜度是多少？
- 時間複雜度為 O(nk+m)。模式串隻需要預處理一次。
- 在 KMP 算法中，對于模式串，我們需要預處理出一個fail 數組（有時也稱為next 數組、π 數組等）。這個數組到底表示了什麼？
- fail[i] 等于滿足下述要求的 x 的最大值：s[0:i]具有長度為 x+1 的完全相同的字首和字尾。這也是 KMP 算法最重要的一部分
🌸解法五: 優化的KMP
如果讀者能夠看懂「正确性證明」和「思考題答案」這兩部分，那麼一定已經發現了方法三中的 KMP 算法有可以優化的地方。即：
- 在「正确性證明」部分，如果我們設 i 為
最小的
- 由于fail[n−1] 表示 s 具有長度為 fail[n−1]+1 的完全相同的（且最長的）字首和字尾。那麼對于滿足題目要求的字元串，一定有 fail[n−1]=n−i−1，即 i=n−fail[n−1]−1；
- 對于不滿足題目要求的字元串，n 一定不是 n −fail[n−1]−1 的倍數
上述所有的結論都可以很容易地使用反證法證出。
是以，我們在預處理出fail 數組後，隻需要判斷 n 是否為 n - fail[n−1]−1 的倍數即可。
public boolean repeatedSubstringPattern4(String s) {
return kmp(s);
}
public boolean kmp(String pattern) {
int n = pattern.length();
int[] fail = new int[n];
Arrays.fill(fail, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
fail[i] = j + 1;
}
}
return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
}