수업 목표

본 수업은 문자열이라는 특수한 자료 구조에 특화된 검색, 비교, 패턴 매칭 알고리즘들을 이해하고 파이썬으로 효율적으로 구현할 수 있는 역량을 배양하는 것을 목표로 합니다. - 트라이(Trie) 자료 구조의 노드 삽입 및 탐색 구조를 이해하고 문자열 집합에서의 $O(L)$ 검색을 구현합니다. - 다항 롤링 해시(Polynomial Rolling Hash) 기법을 활용하여 $O(N)$ 전처리 후 임의의 부분 문자열 동일성을 $O(1)$에 판별합니다. - 실패 함수(Failure Function)를 활용하는 KMP 알고리즘으로 텍스트 $T$ 내에서 패턴 $P$가 출현하는 모든 위치를 $O(|T| + |P|)$에 탐색합니다. - 접미사 배열(Suffix Array)과 LCP(최장 공통 접두사) 배열을 구성하여 문자열에서 두 번 이상 출현하는 가장 긴 반복 부분 문자열을 구합니다.

학습 동기부여

구글 검색 엔진은 수천억 개의 웹 문서 중에서 불과 0.5초 만에 키워드를 찾아내고, 바이오 인포매틱스 분야에서는 수십억 염기쌍으로 이루어진 게놈 서열에서 특정 유전자 패턴을 실시간으로 검색합니다. 이를 가능하게 하는 것이 바로 트라이(Trie), 롤링 해시, KMP, 접미사 배열과 같은 문자열 전용 알고리즘들입니다. 일반적인 이중 루프 완전 탐색 $O(N \cdot M)$으로는 단 수만 개의 문자열 쿼리만 주어져도 타임아웃이 발생하지만, 이 단원에서 배우는 기법들을 적용하면 수백만 건의 문자열 비교도 순식간에 처리할 수 있는 고성능 시스템을 구축할 수 있습니다.

도입 스토리

텍스트 편집기의 "찾기 및 바꾸기" 기능을 사용할 때, 긴 문서에서 짧은 단어를 찾아주는 작업이 필요합니다. 브루트포스 방식으로 단어를 처음부터 끝까지 비교하다가 불일치가 발생하면 한 칸씩 이동하며 다시 비교하는 방식은 최악의 경우 $O(|T| \cdot |P|)$가 됩니다. 하지만 패턴 내부에 반복되는 구조를 미리 계산한 '실패 함수(pi 배열)'를 만들어 두면, 불일치가 일어났을 때 이미 일치한 부분을 건너뛰면서 단 한 번의 선형 탐색으로 모든 일치 위치를 찾아낼 수 있습니다. 문자열의 비밀 구조를 활용하는 스마트한 검색 알고리즘들의 세계로 들어가 봅시다.

1. 트라이 (Trie)

트라이는 문자열 집합을 저장하기 위한 트리 구조입니다. 각 노드가 문자 한 글자를 나타내며, 루트에서 특정 노드까지의 경로를 이어붙이면 하나의 문자열이 완성됩니다. 단어 삽입과 검색 모두 단어 길이 $L$에 비례하여 $O(L)$에 수행됩니다.

# 8069번: 단어 탐색 — Trie 자료 구조 기반 O(L) 탐색
import sys
input = sys.stdin.readline

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

def solve_trie():
    n, m = map(int, input().split())
    trie = Trie()
    for _ in range(n):
        trie.insert(input().strip())
    result = []
    for _ in range(m):
        result.append("1" if trie.search(input().strip()) else "0")
    print("\n".join(result))

solve_trie()

2. 문자열 해싱 (Rolling Hash)

롤링 해시는 다항 함수 $H(s) = s[0] \cdot B^{n-1} + s[1] \cdot B^{n-2} + \dots + s[n-1]$ (mod $M$)으로 문자열에 고유한 정수 값을 부여하여 비교를 수행합니다. 전체 문자열의 해시 배열을 $O(N)$에 전처리해 두면, 임의의 구간 해시를 $O(1)$에 계산하여 부분 문자열 일치 여부를 즉각 판별합니다.

# 8070번: 문자열 해싱 — Rolling Hash O(N) 전처리 후 O(1) 쿼리
import sys
input = sys.stdin.readline

def solve_hash():
    s = input().strip()
    q = int(input())
    n = len(s)
    
    MOD = (1 << 61) - 1  # 메르센 소수 이용
    BASE = 131
    
    # 전처리: 해시 누적 배열과 거듭제곱 배열
    h = [0] * (n + 1)
    pw = [1] * (n + 1)
    for i in range(n):
        h[i + 1] = (h[i] * BASE + ord(s[i])) % MOD
        pw[i + 1] = (pw[i] * BASE) % MOD
    
    def get_hash(l, r):  # 1-indexed, inclusive
        return (h[r] - h[l - 1] * pw[r - l + 1]) % MOD
    
    result = []
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        if (b - a) != (d - c):
            result.append("0")
        elif get_hash(a, b) == get_hash(c, d):
            result.append("1")
        else:
            result.append("0")
    print("\n".join(result))

solve_hash()

3. KMP 패턴 매칭

KMP 알고리즘은 두 단계로 구성됩니다. 먼저 패턴 내부의 접두사-접미사 일치 길이를 기록한 실패 함수($\pi$ 배열)를 $O(|P|)$에 계산합니다. 그 후 텍스트를 선형으로 탐색하면서 불일치 발생 시 $\pi$ 배열을 참조하여 이전 일치 구간을 건너뛰어 $O(|T|)$에 모든 패턴 위치를 탐색합니다.

# 8071번: 패턴 매칭 — KMP O(|T| + |P|) 탐색
import sys
input = sys.stdin.readline

def kmp(t, p):
    n, m = len(t), len(p)
    # 1단계: 실패 함수(pi 배열) 구축
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
            
    # 2단계: 텍스트에서 패턴 탐색
    matches = []
    j = 0
    for i in range(n):
        while j > 0 and t[i] != p[j]:
            j = pi[j - 1]
        if t[i] == p[j]:
            if j == m - 1:
                matches.append(i - m + 2)  # 1-indexed 시작 위치
                j = pi[j]
            else:
                j += 1
    return matches

t = input().strip()
p = input().strip()
result = kmp(t, p)
print(len(result))
print(*result)

4. 접미사 배열과 LCP 배열

접미사 배열(Suffix Array)은 문자열의 모든 접미사를 사전 순으로 정렬한 배열입니다. 인접한 두 접미사 사이의 최장 공통 접두사(LCP) 배열을 구하면, 이 LCP 배열의 최댓값이 곧 두 번 이상 등장하는 가장 긴 부분 문자열의 길이가 됩니다.

# 8072번: 가장 긴 반복 부분 문자열 — Suffix Array + LCP
import sys
input = sys.stdin.readline

def build_suffix_array(s):
    n = len(s)
    sa = sorted(range(n), key=lambda i: s[i:])
    return sa

def lcp(s, sa):
    n = len(s)
    max_lcp = 0
    for i in range(n - 1):
        a, b = sa[i], sa[i + 1]
        common = 0
        while a + common < n and b + common < n and s[a + common] == s[b + common]:
            common += 1
        max_lcp = max(max_lcp, common)
    return max_lcp

s = input().strip()
sa = build_suffix_array(s)
print(lcp(s, sa))

자주 하는 실수 & 오류 예방

- KMP 실패 함수 off-by-one 에러: 실패 함수 배열 pi의 인덱스 $i$는 패턴의 i번째 문자까지에서의 최장 접두-접미사 일치 길이를 저장합니다. KMP 매칭 시 완전 일치 후 j = pi[j]로 점프해야 다음 패턴과 겹치는 경우도 포함하여 처리할 수 있습니다. - 롤링 해시 해시 충돌 방지: 단일 해시 모듈로를 사용하면 Collision 확률이 존재합니다. 이를 방지하려면 메르센 소수 $(2^{61} - 1)$처럼 큰 소수를 사용하거나, 서로 다른 두 BASE-MOD 쌍을 사용하는 이중 해시(Double Hashing) 기법을 적용합니다. - 파이썬 문자열 슬라이싱과 직접 비교의 한계: s[a:b] == s[c:d]처럼 슬라이싱으로 직접 비교하면 매 쿼리마다 $O(L)$이 소요되어 수만 개의 쿼리에서 타임아웃이 발생합니다. 반드시 해시 전처리 배열을 통한 $O(1)$ 비교를 사용해야 합니다.

핵심 정리

알고리즘	전처리 복잡도	쿼리 복잡도	공간 복잡도	주요 활용
트라이 (Trie)	$O(N \cdot L)$	$O(L)$	$O(N \cdot L \cdot |\Sigma|)$	사전 검색, 자동완성, 접두사 공유 집합 관리
롤링 해시	$O(N)$	$O(1)$	$O(N)$	부분 문자열 동일성 판별, 라빈-카프 패턴 매칭
KMP 매칭	$O(|P|)$ (pi 배열)	$O(|T|)$ (탐색)	$O(|P|)$	텍스트 내 패턴 전체 출현 위치 탐색
접미사 배열 + LCP	$O(N \log N)$	$O(1)$ (LCP 최대)	$O(N)$	가장 긴 반복 부분 문자열, 공통 부분 문자열 탐색

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8069	단어 탐색	CSES	보통	트라이(Trie) 삽입 및 검색
8070	문자열 해싱	CSES	보통	롤링 해시 전처리 & $O(1)$ 쿼리
8071	패턴 매칭	CSES	보통	KMP 실패 함수 & 선형 탐색
8072	가장 긴 반복 부분 문자열	CSES	어려움	접미사 배열(Suffix Array) & LCP