브루트 포스 문자열 검색

Foundation을 임포트하지 않고 NSString의 rangeOfString() 메서드를 사용할 수 없는 상황에서 순수 Swift로 문자열 검색 알고리즘을 어떻게 작성할 수 있을까? 목표는 String에 indexOf(pattern: String) 확장을 구현하는 것이다. 이 확장은 검색 패턴의 첫 번째 등장 위치를 나타내는 String.Index를 반환하거나, 패턴을 찾지 못한 경우 nil을 반환한다.

예를 들어:

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

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

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

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

참고: 소 이모지의 인덱스는 6이다. 이모지는 문자당 더 많은 저장 공간을 사용하므로 예상과 달리 3이 아니다. String.Index의 실제 값은 중요하지 않으며, 문자열에서 올바른 문자를 가리키기만 하면 된다.

다음은 브루트 포스 방식의 해결책이다:

extension String {
  func indexOf(_ pattern: String) -> String.Index? {
    for i in self.characters.indices {
        var j = i
        var found = true
        for p in pattern.characters.indices{
            if j == self.characters.endIndex || self[j] != pattern[p] {
                found = false
                break
            } else {
                j = self.characters.index(after: j)
            }
        }
        if found {
            return i
        }
    }
    return nil
  }
}

이 코드는 소스 문자열의 각 문자를 순차적으로 확인한다. 만약 문자가 검색 패턴의 첫 번째 문자와 일치하면, 내부 루프가 패턴의 나머지 부분이 일치하는지 확인한다. 일치하지 않으면 외부 루프는 중단된 지점에서 계속 진행한다. 이 과정은 완전한 일치를 찾거나 소스 문자열의 끝에 도달할 때까지 반복된다.

브루트 포스 방식은 간단하지만 효율적이거나 우아하지는 않다. 작은 문자열에서는 잘 동작하지만, 대량의 텍스트를 다룰 때는 더 나은 알고리즘을 사용하는 것이 좋다. 더 효율적인 알고리즘을 원한다면 Boyer-Moore 문자열 검색을 확인해 보자.

Swift Algorithm Club의 Matthijs Hollemans가 작성함