String Matching & Automata

1. Overview

문자열 매칭과 오토마톤(String Matching & Automata)은 텍스트 T에서 패턴 P를 검색하는 "편집기의 Ctrl+F"부터 바이러스 시그니처 탐지, 게놈 서열 분석까지 모든 문자열 탐색 엔진의 수학적 기반을 구축하는 알고리즘 공학입니다.

학습자는 단순한 Brute-Force O(nm) 탐색이 왜 현실에서 실패하는지를 확인하고, KMP(Knuth-Morris-Pratt) 알고리즘이 이전에 매칭 실패한 정보를 실패 함수(Failure Function)로 재활용하여 O(n+m)에 매칭하는 역학을 뜯어봅니다. 나아가 **Rabin-Karp의 해시 롤링(Rolling Hash)**으로 다중 패턴을 동시 탐색하는 기법을 해부합니다. 마지막으로 문자열 패턴을 상태 전이 다이어그램으로 모델링하는 **유한 오토마톤(Finite Automaton)**과 정규 표현식(RegEx)의 NFA→DFA 변환까지 장악하여 파서(Parser), 렉서(Lexer) 설계 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Brute-Force 탐색과 한계 (Naive Matching): O(nm) 탐색, 최악 케이스 분석.
• KMP 알고리즘 (KMP): 실패 함수(Failure Function / Partial Match Table), 탐색 O(n+m), 전처리 O(m).
• Rabin-Karp (Rolling Hash): 해시 롤링, 다중 패턴 동시 탐색, 해시 충돌 처리.
• 유한 오토마톤과 정규 표현식 (Automata & RegEx): 결정적/비결정적 유한 오토마톤(DFA/NFA), Thompson's Construction(NFA 구축), 부분집합 구성법(Subset Construction, NFA→DFA), 정규 표현식 패턴 매칭.

Out-of-Scope

• Aho-Corasick 다중 패턴: Trie + 실패 링크 기반 멀티 패턴 $\rightarrow$ 04-02-04. Tries & Suffix Trees 영역.
• 문맥 자유 문법(CFG) / 푸시다운 오토마톤(PDA): 프로그래밍 언어 파서 $\rightarrow$ 05-01. Language Theory & Type Systems 영역.

Boundaries

• KMP vs Boyer-Moore vs Rabin-Karp: KMP는 O(n+m)이며 패턴 전처리가 O(m)으로 단일 패턴 탐색의 표준. Boyer-Moore는 평균 O(n/m)으로 KMP보다 빠를 수 있으며 역방향 탐색. Rabin-Karp는 O(n+m) 평균이지만 해시 충돌로 O(nm) 최악 케이스가 있고, 다중 패턴 동시 탐색에 독보적.

3. Counterexample

• KMP 실패 함수 오구현의 무한 루프 (Wrong KMP Failure Function): KMP 실패 함수를 fail[i] = fail[i-1]+1 (단순 증가)로 잘못 계산하면, 실제 재사용 가능한 접두사 경계가 올바르게 계산되지 않습니다. 탐색 중 불일치 발생 시 j = fail[j-1]로 이동해야 하는데, 잘못된 실패 함수로 인해 j가 잘못된 위치로 이동하여 이미 비교한 구간을 재비교하거나 무한 루프에 빠지는 구현 버그입니다.
• 롤링 해시 충돌의 오탐 (Rolling Hash False Positive): Rabin-Karp에서 해시 충돌(두 다른 문자열이 같은 해시값)이 발생할 때 문자열 동등성을 추가 검증(문자 대 문자 비교)하지 않으면, 패턴이 실제로 없는데 있다고 잘못 보고(False Positive)하는 실수. 금융 데이터나 바이러스 탐지에서 이 오탐은 치명적 오류를 낳습니다.

4. Prerequisites

• 문자열 기초 (Basic): ASCII/UTF-8 인코딩, 문자열 인덱싱, 슬라이싱. (04-01-01 Arrays & Strings)
• 해시 함수 (Recommended): Rabin-Karp의 Polynomial Rolling Hash 이해를 위해 해시 함수 개념이 필요합니다. (04-02-03 Hash Tables)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 실패에서 배우는 건너뛰기, KMP 알고리즘 (KMP String Matching)

• Why to Learn: 텍스트 에디터 검색(Ctrl+F), 생물정보학 DNA 서열 탐색, 침입 탐지 시스템(IDS)에서 O(nm) Brute-Force의 한계를 넘어, 불일치 정보를 재활용하는 O(n+m)의 우아한 최적화를 장악하기 위함입니다.
• What to Learn:
  • Concepts: 실패 함수(Failure Function, fail[i] = 패턴 P[0..i]의 진정한 접두사=접미사 최장 길이), 탐색 시 불일치 발생 시 j = fail[j-1] 점프.
  • Skills: 실패 함수 전처리 O(m), KMP 탐색 O(n), 전체 O(n+m).
• How to Learn:
  • 1단계: 패턴 "ABABC" 실패 함수 계산. fail[0]=0, fail[1]=0, fail[2]=1(A=A), fail[3]=2(AB=AB), fail[4]=0(C≠A). 역학: fail[i]는 P[0..i]의 접두사이자 접미사인 최장 부분의 길이를 해부합니다.
  • 2단계: 텍스트 "ABABABABC"에서 패턴 "ABABC" 탐색. i=4에서 불일치(C≠A) 발생. j = fail[j-1] = fail[3] = 2. j를 0으로 초기화하지 않고 2로 점프(이미 매칭된 "AB" 재활용)하여 i 후퇴 없이 탐색 계속하는 역학을 뜯어봅니다.
• Implement: 파이썬 kmp_search(text, pattern). build_failure(pattern) O(m) + kmp_match(text, pattern, fail) O(n). text="AABAACAADAABAABA", pattern="AABA" → 매칭 위치 [0, 9, 12] 출력. Brute-Force vs KMP 비교 문자 비교 횟수 로그.

Recommended

Core Topic 02: 창문을 밀며 해시를 재계산, 롤링 해시와 Rabin-Karp (Rolling Hash)

• Why to Learn: 문서 표절 검사(다수의 짧은 패턴을 긴 텍스트에서 동시 탐색), 데이터 동기화(rsync의 블록 롤링 해시), DNA 반복 서열 탐지의 핵심인 롤링 해시의 O(1) 업데이트 수학을 꿰기 위함입니다.
• What to Learn:
  • Concepts: Polynomial Rolling Hash h(s[i..i+m-1]), 새 문자 추가 + 오래된 문자 제거 O(1) 업데이트(h = (h * BASE + new_char - old_char * BASE^m) % MOD), 해시 충돌 처리.
  • Skills: 다중 패턴 탐색(패턴 해시 Set에 텍스트 윈도우 해시 비교), rsync 차분 동기화 원리.
• How to Learn:
  • 1단계: 윈도우 크기 3으로 "abcde" 탐색. 첫 윈도우 h("abc") 계산. 다음 윈도우 h("bcd") = (h("abc") * BASE - ord('a') * BASE^3 + ord('d')) % MOD. 앞 문자 제거 + 새 문자 추가 O(1) 롤링 연산을 해부합니다.
  • 2단계: 다중 패턴 ["xyz","abc","bcd"]의 해시를 Set에 저장. 텍스트 "abcxyzdef" 슬라이딩 윈도우로 스캔하며 윈도우 해시가 Set에 있으면 실제 문자 비교로 충돌 검증하는 역학을 뜯어봅니다.
• Implement: 파이썬 rabin_karp(text, pattern). BASE=31, MOD=10^9+7. 롤링 해시로 패턴 매칭 위치 반환. rabin_karp_multi(text, patterns) 여러 패턴 동시 탐색. 충돌률 테스트: 1000개 랜덤 패턴 탐색에서 False Positive 발생률 측정.

Practical

Core Topic 03: 정규 표현식의 철학, DFA/NFA 오토마톤 (Automata & RegEx)

• Why to Learn: 정규 표현식(/\d{3}-\d{4}/)이 내부적으로 어떻게 상태 전이 다이어그램(DFA/NFA)으로 변환되어 O(n) 선형 시간에 패턴을 매칭하는지, 파이썬 re 모듈, 렉서(Lexer), 컴파일러 전단부(Frontend)의 심장을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 유한 오토마톤(FA): 상태(State), 전이(Transition), 시작 상태, 수락 상태. DFA(결정적, 각 상태에서 입력당 전이 1개) vs NFA(비결정적, ε-전이 포함). Thompson's Construction(RegEx → NFA), 부분집합 구성법(NFA → DFA).
  • Skills: 정규 표현식 패턴 → NFA 상태 전이도 그리기, DFA 최소화.
  • Tools: Python re 모듈 내부(PCRE 기반).
• How to Learn:
  • 1단계: RegEx (a|b)*abb를 Thompson's Construction으로 NFA로 변환. a|b → OR 분기 2개 상태. * → ε-루프. 문자 abb → 직렬 전이. 전체 NFA의 상태 전이도를 해부합니다.
  • 2단계: NFA를 DFA로 부분집합 구성법 변환. NFA의 ε-closure(ε-전이로 도달 가능한 상태 집합)를 DFA의 단일 상태로 묶어 결정적 전이 테이블 구축. 최종 DFA로 "aabb" → 수락, "ab" → 거부 판정을 뜯어봅니다.
• Implement: 파이썬 간단 DFA 시뮬레이터. DFA(states, transitions, start, accept_states) 클래스. run(input_string) → True/False. (a|b)*abb 패턴 DFA로 "aabb", "babb", "ab", "aa" 수락/거부 정확성 검증.

Advanced

Core Topic 04: 뒤에서 앞으로 나쁜 문자를 피해, Boyer-Moore 알고리즘 (Boyer-Moore)

• Why to Learn: 실무에서 Unix grep, 많은 상용 검색 엔진의 내부 구현인 Boyer-Moore는 패턴을 오른쪽에서 왼쪽으로 비교하고, 불일치 문자 정보(Bad Character)와 접미사 정보(Good Suffix)를 이용해 평균 O(n/m)으로 KMP보다 현실에서 훨씬 빠른 성능을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: Bad Character Rule(불일치 문자가 패턴에 마지막 등장한 위치로 이동), Good Suffix Rule(불일치 전 매칭된 접미사를 패턴 내 다른 등장 위치로 정렬), Galil Rule.
  • Skills: Bad Character 테이블 O(|Σ|m) 전처리, Good Suffix 테이블 O(m) 전처리.
• How to Learn:
  • 1단계: Bad Character: 텍스트에서 불일치 문자 c가 발생했을 때, 패턴 내 c의 가장 오른쪽 등장 위치까지 패턴을 오른쪽으로 이동. c가 패턴에 없으면 패턴 전체를 건너뜀으로 대규모 점프가 발생하는 역학을 해부합니다.
  • 2단계: Good Suffix: 패턴 끝 j자리가 매칭된 상태에서 불일치 발생. 매칭된 접미사 P[j+1..m-1]가 패턴 내 다른 위치에 있으면 그 위치로 정렬. 없으면 접미사의 접두사가 패턴 접두사와 일치하는 위치로 이동하는 역학을 뜯어봅니다.
• Implement: 파이썬 boyer_moore_search(text, pattern). Bad Character 테이블만 구현(Simplified BM). text="ABAAABCD", pattern="ABC" 탐색 시 이동 거리 로그. KMP vs BM 영문 텍스트 1MB 탐색 실제 시간 비교 벤치마크.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Text Processing) — Search patterns.
• [P1] CS2023 - AL/Algorithms and Complexity (Advanced String Matching) — Core requirements.

Secondary

• [Algorithms on Strings] Maxime Crochemore — Theoretical string matching.
• [Compilers: Principles, Techniques, and Tools (Dragon Book)] Aho — Automata foundations.

Industry

• [Google RE2: A principled approach to regular expression matching] — Real-world industry standard.
• [Elasticsearch: Lucene Automata-based Search] — Search engine implementation.

9. Final Checklist

Primary

• 'KMP 알고리즘'의 실패 함수가 왜 패턴의 '가장 긴 경계(Border)' 정보와 물리적으로 일치하는지 설명 가능한가? (P1)
• 'Boyer-Moore'가 왜 텍스트가 무작위일수록(예: 영문 소설) 'Naive' 방식보다 물리적으로 수십 배 빠른지 입증할 수 있는 가? (P1)

Secondary

• 유한 오토마타에서 DFA와 NFA의 물리적 실행 메모리 차이와 검색 속도의 우열을 수리적으로 소통 가능한가?
• 라빈-카프(Rabin-Karp) 알고리즘에서 해시 충돌(Hash collision)이 발생했을 때의 물리적 대응 절차를 도출할 수 있는 가?

Industry

• 고성능 네트워크 방화벽 설계 시, 수천 개의 악성 시그니처를 실시간으로 탐색하기 위해 왜 아호-코라식이 물리적으로 필수적인지 기술할 수 있는 가? (SFIA)
• 정규 표현식 엔진 도입 시, 백트래킹으로 인한 '스택 오버플로우' 지연 공격을 방지하기 위한 보안적 최적화 방안을 제안할 수 있는 가?