聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來，為方便大家閱讀。如果英語閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂部查看所有原文饺律，以便快速學(xué)習(xí)。作者同時(shí)也在學(xué)習(xí)中跺株，歡迎交流
摩爾算法的目的：用swift寫出一個(gè)字符搜索算法复濒，不需要引入Foundation或者使用NSString中的rangeOfString()函數(shù)。
換句話說乒省，我們想要在string上實(shí)現(xiàn)一個(gè)indexOf(pattern: String)方法的拓展巧颈，可以用來檢索指定字符串里是否存在pattern并得到它的String.Index值，或者當(dāng)這個(gè)pattern無法檢索到的時(shí)候袖扛，返回nil砸泛。
示例：
// Input:
let s = "Hello, World"
s.indexOf(pattern: "World")
// Output:
<String.Index?> 7
// Input:
let animals = "??????????"
animals.indexOf(pattern: "??")
// Output:
<String.Index?> 6
注意： 這里奶牛的索引值是6而不是3。因?yàn)樵谧址锩媲猓恳粋€(gè)emoji的字符使用更多的存儲(chǔ)空間唇礁。String.Index的真實(shí)數(shù)字并不重要，只要它能得到字符在字符串里所在的正確位置即可惨篱。
通常情況下盏筐，暴力檢索運(yùn)行效率尚可，但是在檢索大量數(shù)據(jù)的時(shí)候砸讳，這樣的過程并不是很高效琢融。因?yàn)榻Y(jié)果往往是，你并不需要檢索字符串里面的所有字符－－中間大部分字符都可以直接跳過簿寂。
這個(gè)跳過繼續(xù)檢索的算法叫做摩爾算法吏奸。它存在已久，并且被認(rèn)為是所有字符檢索算法的基準(zhǔn)陶耍。
以下是在swift中我們實(shí)現(xiàn)它的代碼：
extension String {
func index(of pattern: String) -> Index? {
// 存儲(chǔ)pattern的長度值
let patternLength = pattern.characters.count
guard patternLength > 0, patternLength <= characters.count else { return nil }
// 創(chuàng)建跳過表格
// 當(dāng)pattern里的某一個(gè)字符被檢索到，這個(gè)表格可以決定我們可以跳過多少長度
var skipTable = [Character: Int]()
for (i, c) in pattern.characters.enumerated() {
skipTable[c] = patternLength - i - 1
}
// 這里得到pattern里最后一個(gè)字符.
let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]
//
// 核對(duì)過程是由pattern的右向左她混，所以我們跳過的長度為pattern的長度
// 這里扣掉1是因?yàn)閟tartIndex已經(jīng)指向源字符串的首字符位置
var i = index(startIndex, offsetBy: patternLength - 1)
// 此函數(shù)將源字符串和pattern從指定位置開始對(duì)比匹配烈钞，當(dāng)對(duì)應(yīng)位置的字符
// 不一致時(shí)候返回nil，反之返回字符串上面經(jīng)過匹配對(duì)比的最前一位的位置
func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}
// 主循環(huán).在找到完全匹配時(shí)候結(jié)束坤按，或者全部檢索完依然沒有匹配時(shí)候返回nil
while i < endIndex {
let c = self[i]
// 檢測(cè)源字符中當(dāng)前位置的字符與pattern的最后一位字符是否相同
if c == lastChar {
// 當(dāng)發(fā)現(xiàn)可能匹配的時(shí)候毯欣，進(jìn)行暴力匹配對(duì)比
if let k = backwards() { return k }
// 如果不匹配，直接前進(jìn)一個(gè)位置.
i = index(after: i)
} else {
// 當(dāng)前字符狀態(tài)為不匹配臭脓，所以需要向前移動(dòng)酗钞，移動(dòng)的距離由跳過表格決定
//如果當(dāng)前字符與pattern沒有任何匹配，則直接前進(jìn)一個(gè)pattern長度的距離。否則砚作，則根據(jù)跳過表格的距離決定窘奏。
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}
算法具體運(yùn)行過程如下：
我們將需要檢索的pattern和源字符串放在一起對(duì)比。從源字符中與pattern的最后一個(gè)字符對(duì)應(yīng)位置的字符開始比較
source string: Hello, World
search pattern: World
^
此時(shí)存在三種可能性：
1.pattern的最后一個(gè)字符與源字符串的對(duì)應(yīng)位置的字符相同葫录，可能會(huì)有匹配
2.pattern的最后一個(gè)字符與源字符串的對(duì)應(yīng)位置的字符不相同着裹，但是源字符串的這個(gè)位置的字符，在pattern里面也存在米同。
3.pattern的最后一個(gè)字符與源字符串的對(duì)應(yīng)位置的字符不相同骇扇，同時(shí)源字符串的這個(gè)位置的字符，在pattern里面不存在面粮。
在上面的示例中少孝，源字符串的o與pattern的'd'并不相同。但是o在pattern里面同樣存在熬苍。所以稍走，我們可以將pattern前進(jìn)幾個(gè)位置，直到pattern的o與源字符串的o在同一個(gè)位置冷溃，如下：
source string: Hello, World
search pattern: World
^
現(xiàn)在兩個(gè)字符串對(duì)應(yīng)的o都在同一個(gè)位置钱磅，我們先從pattern的最后一個(gè)字符開始進(jìn)行匹配對(duì)比。d與W不相同似枕，說明當(dāng)前仍然不匹配盖淡。但是W依然是pattern里面含有的字符，繼續(xù)前進(jìn)到相關(guān)位置：
source string: Hello, World
search pattern: World
^
這一次我們發(fā)現(xiàn)pattern與源字符串里面對(duì)應(yīng)的字符完全匹配凿歼。這里匹配過程由backward函數(shù)檢測(cè)褪迟。
在檢索過程中，每一次要跳過的距離由跳過表格決定答憔。在示例中味赃，pattern的跳過表格如下：
W: 4
o: 3
r: 2
l: 1
d: 0
字符在pattern里面距離最后一個(gè)字符的距離越長，可以跳過的距離也就越長虐拓。如果當(dāng)前決定跳過距離的字符在pattern里出現(xiàn)多次心俗，即跳過表格里面存在同個(gè)字符多個(gè)距離，則選擇最短的距離進(jìn)行跳過蓉驹。
注意：如果需要搜索的pattern只包含少數(shù)字符城榛，則直接用暴力檢索會(huì)更加快速。因?yàn)槲覀冃枰獧?quán)衡創(chuàng)建跳過表格消耗的時(shí)間和直接暴力檢索消耗的時(shí)間态兴。
Boyer-Moore-Horspool 算法
Boyer-Moore-Horspool算法是摩爾算法的變形狠持。和摩爾算法一樣，此算法也是用跳過表格來跳過不需要檢索的字符瞻润，不同點(diǎn)在于如何檢測(cè)部分匹配喘垂。在之前的版本中甜刻，如果我們發(fā)現(xiàn)部分匹配（pattern的最后一個(gè)字符與當(dāng)前位置下源字符里的字符匹配），但是并不是完全匹配正勒，我們選擇向前只跳一個(gè)字符的距離得院。而在這個(gè)版本中，我們會(huì)繼續(xù)使用跳過表格來決定跳過距離昭齐。
以下為Boyer-Moore-Horspool的代碼：
extension String {
func index(of pattern: String) -> Index? {
// 存儲(chǔ)pattern的長度值
let patternLength = pattern.characters.count
guard patternLength > 0, patternLength <= characters.count else { return nil }
// 創(chuàng)建跳過表格
// 當(dāng)pattern里的某一個(gè)字符被檢索到尿招，這個(gè)表格可以決定我們可以跳過多少長度
var skipTable = [Character: Int]()
for (i, c) in pattern.characters.enumerated() {
skipTable[c] = patternLength - i - 1
}
// 這里得到pattern里最后一個(gè)字符.
let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]
// 核對(duì)過程是由pattern的右向左，所以我們跳過的長度為pattern的長度
// 這里扣掉1是因?yàn)閟tartIndex已經(jīng)指向源字符串的首字符位置
var i = index(startIndex, offsetBy: patternLength - 1)
// 此函數(shù)將源字符串和pattern從指定位置開始對(duì)比匹配阱驾，當(dāng)對(duì)應(yīng)位置的字符
// 不一致時(shí)候返回nil就谜，反之返回字符串上面經(jīng)過匹配對(duì)比的最前一位的位置
func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}
// 主循環(huán).在找到完全匹配時(shí)候結(jié)束，或者全部檢索完依然沒有匹配時(shí)候返回nil
while i < endIndex {
let c = self[i]
// 檢測(cè)源字符中當(dāng)前位置的字符與pattern的最后一位字符是否相同
if c == lastChar {
// 當(dāng)發(fā)現(xiàn)可能匹配的時(shí)候里覆，進(jìn)行暴力匹配對(duì)比
if let k = backwards() { return k }
// 確保至少向前進(jìn)1個(gè)字符的距離丧荐，因?yàn)槲覀冏钤玳_始檢索的時(shí)候，第一個(gè)可能匹配的字符也出現(xiàn)在跳過表格里面
//而跳過表格提供的跳過距離為0喧枷，如果不限制的話檢索無法繼續(xù)
let jumpOffset = max(skipTable[c] ?? patternLength, 1)
i = index(i, offsetBy: jumpOffset, limitedBy: endIndex) ?? endIndex
} else {
// 當(dāng)前字符狀態(tài)為不匹配虹统，所以需要向前移動(dòng)，移動(dòng)的距離由跳過表格決定
//如果當(dāng)前字符與pattern沒有任何匹配隧甚，則直接前進(jìn)一個(gè)pattern長度的距離车荔。否則，則根據(jù)跳過表格的距離決定戚扳。
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}
總的來說忧便，此版本的摩爾算法較優(yōu)于一開始的版本。但是同樣的帽借，在使用過程中珠增，仍然需要權(quán)衡一下pattern和源字符串的長度。這樣算法才能真正的幫助你提高效率砍艾。
