알고리즘과 자료 구조 - 기초 - 보이어무어 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 table을 활용한다.
HELLO라는 문자열을 찾고싶을 때,
H는 skip 테이블에 있고, skip table을 보면 인덱스를 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