Boyer-Moore 문자열 검색

// 입력:
let s = "Hello, World"
s.indexOf(pattern: "World")

// 출력:
<String.Index?> 7

// 입력:
let animals = "🐶🐔🐷🐮🐱"
animals.indexOf(pattern: "🐮")

// 출력:
<String.Index?> 6

extension String {
    func index(of pattern: String) -> Index? {
        // 검색 패턴의 길이를 캐시한다. 여러 번 사용되며 계산 비용이 크기 때문이다.
        let patternLength = pattern.count
        guard patternLength > 0, patternLength <= count else { return nil }

        // 건너뛰기 테이블을 만든다. 이 테이블은 패턴의 문자가 발견되었을 때 얼마나 건너뛸지 결정한다.
        var skipTable = [Character: Int]()
        for (i, c) in pattern.enumerated() {
            skipTable[c] = patternLength - i - 1
        }

        // 패턴의 마지막 문자를 가리킨다.
        let p = pattern.index(before: pattern.endIndex)
        let lastChar = pattern[p]

        // 패턴을 오른쪽에서 왼쪽으로 스캔하므로, 문자열에서 패턴 길이만큼 건너뛴다.
        // (startIndex가 이미 문자열의 첫 문자를 가리키므로 1을 뺀다.)
        var i = index(startIndex, offsetBy: patternLength - 1)

        // 두 문자열을 뒤로 이동하며 일치하지 않는 문자를 찾거나 패턴의 시작에 도달할 때까지 이동하는 헬퍼 함수.
        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
        }

        // 메인 루프. 문자열의 끝에 도달할 때까지 계속 진행한다.
        while i < endIndex {
            let c = self[i]

            // 현재 문자가 패턴의 마지막 문자와 일치하는가?
            if c == lastChar {

                // 가능한 일치가 있다. 브루트 포스 검색을 뒤로 진행한다.
                if let k = backwards() { return k }

                // 일치하지 않으면 한 문자만 건너뛰는 것이 안전하다.
                i = index(after: i)
            } else {
                // 문자가 일치하지 않으면 건너뛴다. 건너뛰는 양은 건너뛰기 테이블에 의해 결정된다.
                // 문자가 패턴에 없으면 패턴 길이만큼 건너뛸 수 있다. 그러나 패턴에 문자가 있으면
                // 앞에 일치가 있을 수 있으므로 그렇게 많이 건너뛸 수 없다.
                i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
            }
        }
        return nil
    }
}

extension String {
    func index(of pattern: String) -> Index? {
        // 검색 패턴의 길이를 캐싱한다. 여러 번 사용될 예정이며 계산 비용이 크기 때문이다.
        let patternLength = pattern.count
        guard patternLength > 0, patternLength <= characters.count else { return nil }

        // skip 테이블을 만든다. 이 테이블은 패턴의 문자가 발견되었을 때 얼마나 건너뛸지 결정한다.
        var skipTable = [Character: Int]()
        for (i, c) in pattern.enumerated() {
            skipTable[c] = patternLength - i - 1
        }

        // 패턴의 마지막 문자를 가리킨다.
        let p = pattern.index(before: pattern.endIndex)
        let lastChar = pattern[p]

        // 패턴은 오른쪽에서 왼쪽으로 스캔되므로, 문자열에서 패턴 길이만큼 건너뛴다. 
        // (startIndex가 이미 소스 문자열의 첫 번째 문자를 가리키므로 1을 뺀다.)
        var i = index(startIndex, offsetBy: patternLength - 1)

        // 이 헬퍼 함수는 두 문자열을 뒤로 돌아가며 스캔한다.
        // 일치하지 않는 문자를 찾거나 패턴의 시작에 도달할 때까지 진행한다.
        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
        }

        // 메인 루프. 문자열의 끝에 도달할 때까지 계속 진행한다.
        while i < endIndex {
            let c = self[i]

            // 현재 문자가 패턴의 마지막 문자와 일치하는가?
            if c == lastChar {

                // 가능한 일치가 있다. 뒤로 돌아가며 브루트 포스 검색을 수행한다.
                if let k = backwards() { return k }

                // 최소 한 문자는 건너뛰도록 한다. (skipTable[lastChar] = 0이므로 필요하다.)
                let jumpOffset = max(skipTable[c] ?? patternLength, 1)
                i = index(i, offsetBy: jumpOffset, limitedBy: endIndex) ?? endIndex
            } else {
                // 문자가 일치하지 않으므로 skip 테이블에 따라 건너뛴다. 
                // 문자가 패턴에 없으면 전체 패턴 길이만큼 건너뛸 수 있다. 
                // 하지만 패턴에 문자가 존재한다면 앞쪽에서 일치가 있을 수 있으므로 더 적게 건너뛴다.
                i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
            }
        }
        return nil
    }
}