ベース-ボイル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번째 인덱스겠징?

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