最近在leetcode上刷題，當然熔萧，是用swift，中間的辛酸經(jīng)歷就不提了贮缕，不得不說swift在便利性上的確十分強大俺榆，但其效率也的確相較C++、JAVA等顯得相對低下罐脊，在這里不得不吐槽leetcode的Time Limit Exceeded魔咒似乎并不隨著語言環(huán)境的不同而有所改變蜕琴，每當看著Top solutions上一些C++凌简、JAVA信徒用同樣的算法打敗了Time Limit Exceeded魔咒而我卻一次又一次在魔咒面前止步不得不說我感到我的心在滴血恃逻。
然而就是又一次在刷題苦于ime Limit Exceeded魔咒時看到了KMP算法，當即被晦澀難懂的理論砸的懵逼了寇损，在好半天的理解加題目應用才逐漸明白過來矛市。
KMP算法的原理可以看這篇，在這么多篇的博文中這篇算是我看過最淺顯易懂的了尘盼。
我只是將KMP算法的原理通過實際題目以自我的理解剖析一遍。
算法題是這樣的：
Repeated Substring Pattern
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"
Output: False
Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
簡單明了的算法題配紫，給你一個不為空的字符串午阵，你需要通過算法得出這個字符串中是否有字符成循環(huán)關系，返回布爾值植袍。
簡單的審題我們可以寫成這樣的偽代碼籽懦。
//for循環(huán)套for循環(huán)。
//外層的循環(huán)從字符串的0下標開始截取每一個字符組成字符串暮顺。
//內層的循環(huán)從外層字符串的長度+1開始循環(huán)，截取之后的每個字符組成字符串并與外層的可變字符進行比較
//定義一個變量羽氮，當內層字符串與外層字符串相同時+=1惫恼，若變量在跳出內層循環(huán)時的值與原始字符串的長度 / 外層字符串的長度 - 1（外層字符串的長度） 的值相等則輸出True，否則輸出False令宿。
通過偽代碼你即可看出這是多繁復的寫法了，當然我們可以通過加上一些條件進行篩選而減少步驟掀淘，例如
//若外層字符串與內層字符串長度不相等則不進行比較
//若外層字符串長度 % 原始字符串長度不為0則不進行內部循環(huán)
等等油昂。
這些篩選條件的確讓內部操作減少但也讓代碼變得更加繁瑣，而且就算這樣也沒抵擋地住Time Limit Exceeded魔咒拦惋。
那么安寺，換一種思考法，我們通過截取字符串并讓它循環(huán)增殖再與原字符串比較挑庶，如此，是否更高效举畸？
func repeatedSubstringPattern(_ str: String) -> Bool {
for i in (1...str.characters.count/2).reversed(){
if str.characters.count % i == 0 {
let s = str.substring(to: str.index(str.startIndex, offsetBy: i))
var s2 = ""
let m = str.characters.count / s.characters.count
for _ in 0..<m{
s2.append(s)
}
if s2 == str { return true }
}
}
return false
}
這種方法比起第一種擁有更簡潔的代碼凳枝，并且，其效率相較于第一種也顯得高上一節(jié)（你看外部for循環(huán)都砍一半了叛买，內部for循環(huán)更是只有m次）蹋订。
不得不說Swift的某些字符串操作手法簡直是天怒人怨，截取字符串要寫成這樣
let s = str.substring(to: str.index(str.startIndex, offsetBy: i))
如果要獲得某一個具體位置的字符更是要如此
let sc = str.characters[str.characters.index(str.characters.startIndex, offsetBy: i)]
不要說 for c in s.characters椒功，兩個字符串比較時還是要加個變量記錄位置ORZ
然而玫锋，終究還是抵擋不住魔咒，雖然第二種方法效率高上一截撩鹿，但依然抵擋不住魔咒，（順便一提同樣的代碼我寫了份C++的直接通過了……）
于是在Top solutions我找到了KMP算法
func repeatedSubstringPattern1(_ str: String) -> Bool {
//KMP算法
let length = str.characters.count
//i表示的是下一需要比較的字符串的下標
var i = 1,j = 0
var next = [Int](repeating:0, count:length+1)
while i < length {
if str.characters[str.characters.index(str.characters.startIndex, offsetBy: i)] == str.characters[str.characters.index(str.characters.startIndex, offsetBy: j)] {
//若位置i的字符與j匹配的上則對下一個位置的字符進行比較
//同時键思，對next數(shù)組（即最大公共長度數(shù)組進行更新），其下標中的數(shù)值即是當前的最大公共長度看蚜，即j+=1后的值
i+=1
j+=1
next[i] = j
} else if j == 0 {
//若公共長度為一赔桌，這種情況可能出現(xiàn)在一開始，也就是字符一開始沒有匹配上的時候疾党，亦可能出現(xiàn)在匹配過程中因為匹配不上而不斷切割公共長度，直到公共長度為0時竭钝。
//此時雹洗，將需要比對的字符向后移動一位進行匹配，也就是i+=1
i+=1
} else {
//當字符不匹配而公共長度又不為0時則不斷切割最大公共長度时肿，即前移j在字符串中的位置，也就是將之前保存的next容器中的最大公共長度進行切割港令，獲取j的歷史值
j = next[j]
}
}
return next[length] > 0 && next[length] % (length - next[length]) == 0
}
哈哈哈哈锈颗！龜兒子，就這樣也想難倒我淋淀！
……
