Ch 14. 문자열 알고리즘 (String Algorithms)

Lesson 214. 문자열 알고리즘

String Algorithms: Trie, Rolling Hash, KMP, and Suffix Array - 트라이(Trie) 자료 구조를 활용한 $O(L)$ 단어 삽입 및 탐색 - 롤링 해시(Rolling Hash)로 임의의 부분 문자열을 $O(1)$에 비교 - KMP 실패 함수($\pi$ 배열)를 통한 $O(|T|+|P|)$ 패턴 탐색 - 접미사 배열(Suffix Array) + LCP 배열로 가장 긴 반복 부분 문자열 탐색

수업 목표 및 핵심 역량

- 알파벳 기반 트리인 트라이를 구현하여 문자열 집합의 삽입 및 검색을 최적화합니다. - 해시 전처리 배열을 구축하여 부분 문자열 동일성 쿼리를 상수 시간에 처리합니다. - KMP 실패 함수를 이용하여 비교 횟수를 최소화한 패턴 탐색을 구현합니다. - 접미사 배열과 LCP 배열의 상관 관계를 통해 반복 패턴의 최대 길이를 도출합니다.

트라이 (Trie) 탐색

- 트리 경로를 따라 문자를 한 글자씩 매칭하는 $O(L)$ 검색

# 8069번: 단어 탐색 발췌
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

롤링 해시 구간 비교

- $O(N)$ 전처리 후 $O(1)$ 구간 해시로 부분 문자열 비교

# 8070번: 문자열 해싱 발췌
def get_hash(l, r):  # 1-indexed
    return (h[r] - h[l - 1] * pw[r - l + 1]) % MOD

if get_hash(a, b) == get_hash(c, d):
    result.append("1")

KMP 패턴 매칭

- 실패 함수로 불일치 시 뒤로 이동하는 양 결정

# 8071번: 패턴 매칭 발췌
# 불일치 발생 시 pi 배열로 j 점프
while j > 0 and t[i] != p[j]:
    j = pi[j - 1]
# 완전 매칭 발견 후 다음 가능 위치로 이동
if j == m - 1:
    matches.append(i - m + 2)
    j = pi[j]

접미사 배열 + LCP

- 정렬된 접미사 간 최장 공통 접두사(LCP) 최댓값이 답

# 8072번: 가장 긴 반복 부분 문자열 발췌
sa = sorted(range(n), key=lambda i: s[i:])
# 인접 접미사 쌍에서 LCP 최댓값 산출
for i in range(n - 1):
    a, b = sa[i], sa[i + 1]
    # a, b 위치에서 공통 접두사 길이 측정

오류 예방 및 안정성 체크

- **KMP 완전 일치 후 점프**: 완전 매칭 후 j = pi[j]로 설정해야 이후 겹치는 패턴도 탐지 가능 - **해시 충돌 방지**: 메르센 소수 $(2^{61}-1)$ 사용 또는 이중 해시(Double Hashing) 적용으로 충돌 확률 극소화 - **슬라이싱 직접 비교 금지**: 부분 문자열 쿼리에서 s[a:b] == s[c:d]는 $O(L)$이므로 반드시 해시 배열로 대체