ベース-ボイルBoyer-Moore string search

ブルートフォースを使用する場合

let text = "Hello World"

// Brute
if let i = text.firstIndex(of: "E") {
    print(text[i])
}

// indices는 string의 index를 리턴한다
extension String {
    func index(of pattern: String) -> Index? {
        for i in indices {
            var j = i
            var found = true
            for p in pattern.indices {
                guard j != endIndex && self[j] == pattern[p] else {
                    found = false
                    break
                }
                j = index(after: j)
            }
            if found {
                return i
            }
        }
        return nil
    }
}

text.index(of: "lo")    //String.Index를 리턴함...3번째 인덱스겠징?

Boyer-Moore string search
文字列を逆さまに比較します.
skipテーブルを使用します.
HELLOという文字列を検索すると、
Hはskipテーブルにあり、skipテーブルは4つ以上のインデックスを表す.
最後に緑色Oに移動
文字列を後から比較するときに一致します.
文字列を検索して終了します.

extension String {
    func index(of pattern: String) -> Index? {
        let patternLength = pattern.count
        guard patternLength > 0, patternLength <= count else {
            return nil
        }
        
        let skipTable = pattern.skipTable
        let lastChar = pattern.last!
        
        var i = index(startIndex, offsetBy: patternLength - 1)
        
        while i < endIndex {
            let c = self[i]
            
            if c == lastChar {
                if let k = match(from: i, with: pattern) { return k }
                i = index(after: i)
            } else {
                i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
            }
        }
        
        return nil
    }
    
    fileprivate var skipTable: [Character: Int] {
        var skipTable: [Character: Int] = [:]
        for (i, c) in enumerated() {
            skipTable[c] = count - i - 1
        }
        return skipTable
    }
    
    //recursive
    fileprivate func match(from currentIndex: Index, with pattern: String) -> Index? {
        //bounds checking
        if currentIndex < startIndex { return nil }
        if currentIndex >= endIndex { return nil }
        
        //매치하지 않을 때 더 이상 진행하지 않음
        if self[currentIndex] != pattern.last { return nil }
        
        if pattern.count == 1 && self[currentIndex] == pattern.last {
            return currentIndex
        }
        
        return match(from: index(before: currentIndex), with: "\(pattern.dropLast())")
    }
}

let helloText = "Hello"
helloText.skipTable.forEach { print($0) }
//(key: "H", value: 4)
//(key: "L", value: 1)
//(key: "O", value: 0)
//(key: "E", value: 3)

let sourceString = "Hello World!"
let pattern = "World"
sourceString.index(of: pattern) //6

基礎って言ったでしょ.
ちっとも知らない
ソース
https://www.raywenderlich.com/541-swift-algorithm-club-boyer-moore-string-search-algorithm