개념

문자열 알고리즘은 글자의 나열을 빠르고 정확하게 다루는 방법을 모은 분야입니다. 편집기의 찾기 기능, 로그 검색, 검색창의 자동 완성, 유전체 서열 비교처럼 "어떤 글자 묶음이 어디에 있는가"를 묻는 일은 모두 문자열 알고리즘 위에서 돌아갑니다. 이 장에서는 이후 장에서 계속 쓸 용어를 정리하고, 가장 단순한 방법인 순진한 매칭부터 출발해 왜 더 나은 알고리즘이 필요한지 살펴봅니다.

기본 용어

"진(proper)" 접두사는 문자열 전체를 뺀 접두사를 말합니다. 경계는 KMP 알고리즘의 핵심이므로 이 장에서 확실히 익혀 두는 것이 좋습니다.

문제의 종류

문자열 알고리즘이 푸는 문제는 크게 네 가지로 나눌 수 있습니다.

• 단일 패턴 검색: 텍스트에서 패턴 하나의 모든 출현 위치를 찾습니다. 순진한 방법, KMP, Z 알고리즘, Rabin-Karp, Boyer-Moore가 여기에 속합니다.
• 다중 패턴 검색: 금칙어 목록처럼 여러 패턴을 한 번에 찾습니다. Aho-Corasick, 해시 집합을 쓰는 Rabin-Karp가 대표적입니다.
• 사전 검색: 단어 목록에서 특정 접두사로 시작하는 단어를 찾습니다. 트라이(trie)가 전형적인 도구입니다.
• 텍스트 색인: 같은 텍스트에 질의가 많이 들어올 때 텍스트를 미리 가공해 둡니다. 접미사 배열이나 FM 인덱스가 쓰입니다.

순진한 매칭

가장 직관적인 방법은 텍스트의 모든 시작 위치에서 패턴을 한 글자씩 비교하는 것입니다.

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    hits = []
    for start in range(n - m + 1):
        j = 0
        while j < m and text[start + j] == pattern[j]:
            j += 1
        if j == m:
            hits.append(start)
    return hits


print(naive_search("abracadabra", "abra"))  # [0, 7]

이 방법은 짧은 텍스트에는 충분합니다. 하지만 텍스트가 aaaa...a이고 패턴이 aaa...ab이면 시작 위치마다 거의 m번을 비교한 뒤 실패하므로 최악의 경우 O(n·m)이 됩니다. 문제는 실패할 때마다 이미 비교해서 알게 된 정보를 버리고 다음 위치에서 처음부터 다시 비교한다는 점입니다. KMP는 이 정보를 경계 표로 저장해 재사용하고, Rabin-Karp는 비교 자체를 해시값 비교로 바꿉니다.

경계를 직접 구해 보기

경계 개념을 손에 익히기 위해 가장 긴 경계를 무식하게 구해 봅니다. 다음 장에서 이 값을 O(m)에 구하는 접두사 함수를 다룹니다.

def longest_border(s: str) -> int:
    for length in range(len(s) - 1, 0, -1):
        if s[:length] == s[-length:]:
            return length
    return 0


for word in ["abcab", "aaaa", "abcd", "ababa"]:
    print(word, longest_border(word))
# abcab 2 / aaaa 3 / abcd 0 / ababa 3

ababa의 가장 긴 경계는 aba로 길이 3입니다. 경계는 서로 겹칠 수 있다는 점에 주의합니다.

언제 직접 구현하는가

Python의 in, str.find, str.count, 그리고 정규 표현식 모듈 re는 이미 잘 최적화되어 있습니다. 실무에서 단순 검색을 위해 KMP를 다시 짤 일은 드뭅니다. 그래도 직접 구현을 알아야 하는 경우가 있습니다.

• 표준 함수가 주지 않는 정보가 필요할 때: 접두사 함수 값, 문자열의 최소 주기, 모든 경계 등
• 스트림처럼 텍스트가 조금씩 들어와 한 번에 넘길 수 없을 때
• 여러 패턴, 접두사 검색, 부분 문자열 해시처럼 표준 함수 범위를 벗어날 때
• 코딩 테스트와 면접에서 시간 복잡도를 설명해야 할 때

유니코드 주의점

"글자"의 정의는 생각보다 단순하지 않습니다. Python의 str은 코드 포인트(code point)의 나열이고, 화면에 보이는 한 글자가 코드 포인트 여러 개일 수 있습니다.

import unicodedata

a = "café"                       # é 하나(U+00E9)
b = "café"                 # e + 결합 악센트(U+0301)
print(a == b, len(a), len(b))    # False 4 5
print(unicodedata.normalize("NFC", a) == unicodedata.normalize("NFC", b))  # True
print(len(a.encode("utf-8")))    # 5 (바이트 수)

검색 전에 텍스트와 패턴을 같은 정규화 형식(NFC 등)으로 맞추지 않으면, 사람 눈에는 같은 단어가 검색되지 않습니다. 이 문제는 마지막 장에서 다시 다룹니다.

정리

• 텍스트 길이는 n, 패턴 길이는 m으로 쓰며, 경계는 접두사이면서 접미사인 진부분 문자열입니다.
• 순진한 매칭은 최악 O(n·m)이며, 실패할 때 얻은 정보를 버리는 것이 약점입니다.
• KMP·Z는 이미 비교한 정보를 재사용하고, Rabin-Karp는 해시로 비교를 줄이며, 트라이는 사전의 접두사 검색을 맡습니다.
• 유니코드 텍스트는 정규화와 "글자" 단위를 먼저 정해야 결과가 기대와 맞습니다.