4. Z 알고리즘 (Z-Algorithm) — 접두사 매칭 배열

핵심 인사이트 (3줄 요약)

1. 본질: Z 알고리즘은 문자열 S의 각 위치 i에서 시작하는 부분 문자열이 S의 접두사(Prefix)와 얼마나 일치하는지를 나타내는 Z 배열 (Z-Array)을 O(n)에 계산하는 알고리즘이다.
2. 가치: Z 배열 하나로 패턴 매칭을 O(n+m)에 수행하며, KMP (Knuth-Morris-Pratt) 실패 함수와 개념적으로 동등하지만 구현이 더 직관적이라는 장점이 있다.
3. 판단 포인트: 단일 패턴 매칭에서 KMP와 동일한 성능을 제공하며, 주기(Period) 탐색·최소 반복 단위 찾기 문제에서 Z 배열이 KMP보다 직접적으로 활용된다.

Ⅰ. 개요 및 필요성

문자열 S = "aabxaa"에서 각 위치가 접두사 "aa"와 얼마나 공통되는지를 O(n²) 브루트포스로 계산하면 긴 문자열에서 느리다. Z 알고리즘은 이미 계산된 Z-box를 재활용하여 O(n)에 Z 배열을 구성한다. 이를 이용하면 텍스트에서 패턴 탐색, 주기 탐색, 문자열 압축을 선형 시간에 수행할 수 있다.

Z 배열 정의

Z[i] = S[i..n-1]과 S[0..n-1]의 최장 공통 접두사 (LCP) 길이
Z[0] = |S| (관례적으로 문자열 전체 길이로 정의)

📢 섹션 요약 비유: Z 배열은 문자열의 각 지점에서 "여기서 시작하는 부분이 문자열 맨 앞과 몇 글자 똑같은가?"를 기록한 이력표다.

Ⅱ. 아키텍처 및 핵심 원리

Z 배열 계산 예시

S = "aabxaabxca"
     0123456789

Z[0] = 10 (전체, 관례)
Z[1] = 1  → S[1..] = "abxaabxca" vs S = "aabxaabxca"
                       a ≠ a (첫 글자만 일치? "a"="a" O, "b"≠"a" X → 1)
Z[2] = 0  → S[2..] = "bxaabxca" vs "aabxaabxca" → b≠a → 0
Z[3] = 0
Z[4] = 4  → S[4..] = "aabxca" vs "aabxaabxca" → "aabx" 일치 → 4
Z[5] = 1
Z[6] = 0  (b vs a)
Z[7] = 0
Z[8] = 0
Z[9] = 1

Z = [10, 1, 0, 0, 4, 1, 0, 0, 0, 1]

Z 알고리즘: Z-box 활용

Z-box: 현재까지 계산된 가장 오른쪽 [l, r] 구간 (S[l..r]이 접두사와 일치)

i를 왼쪽에서 오른쪽으로 처리:
  case 1: i > r → 브루트포스로 Z[i] 계산, Z-box 갱신
  case 2: i ≤ r →
    k = i - l  (i의 Z-box 내 상대 위치)
    if Z[k] < r-i+1: Z[i] = Z[k]  (완전히 Z-box 안)
    else:            i부터 r+1 이후 브루트포스, Z-box 확장

총 문자 비교 횟수: O(n) (각 문자는 Z-box 오른쪽 확장 시 최대 1회)

Z 배열을 이용한 패턴 매칭

패턴 P, 텍스트 T에서 P의 모든 등장 위치 찾기:

1. S = P + "$" + T  ($ = P에도 T에도 없는 구분자)
2. Z 배열 계산: O(|P| + |T|)
3. Z[i] == |P|인 위치 i → T에서 i - |P| - 1 위치에 P 등장

예시: P="aa", T="aabxaa", S="aa$aabxaa"
  Z = [9, 1, 0, 2, 1, 0, 0, 2, 1]
  |P|=2인 Z[3]=2, Z[7]=2 → T의 인덱스 0과 4에 "aa" 등장

📢 섹션 요약 비유: Z 배열을 이용한 패턴 매칭은 패턴을 텍스트 앞에 붙여서 "나와 똑같이 시작하는 부분"을 한 번에 찾는 것—구분자($)가 접두사 길이를 자동으로 제한한다.

Ⅲ. 비교 및 연결

Z 알고리즘 vs KMP 알고리즘

주기 탐색 (Period Finding)

S의 최소 주기 p: S = S[0..p-1]의 반복으로 구성 가능한 최소 p

Z 배열로:
  p가 주기이면 Z[p] >= n-p 이어야 함
  → 모든 i에서 Z[i] >= n-i 인 최소 i가 최소 주기

예: "ababab" → Z = [6,0,4,0,2,0]
  Z[2]=4 >= 6-2=4 ✓ → 최소 주기 p=2 ("ab")

📢 섹션 요약 비유: Z 알고리즘으로 주기를 찾는 것은 타일 패턴에서 가장 작은 반복 단위를 발견하는 것—타일 하나만 보면 전체 패턴을 재현할 수 있는지 확인한다.

Ⅳ. 실무 적용 및 기술사 판단

주요 활용 사례

• 패턴 매칭: 단일 패턴을 텍스트에서 O(n+m) 탐색
• 주기 탐색: DNA 서열의 반복 모티프(Repeat Motif) 탐지
• 문자열 압축: 최소 반복 단위 기반 표현 ("abcabc" → "(abc)×2")
• 문자열 동치 판별: S가 T의 회전(Rotation)인지: Z("T$TT")[m+1] == m
• 공통 접두사 최대화: 여러 문자열 공통 접두사 길이 계산

기술사 판단 기준

단일 패턴 탐색                        →  KMP 또는 Z 알고리즘 (동등)
구현 단순성 우선                      →  Z 알고리즘 (직관적)
주기/반복 단위 탐색                   →  Z 알고리즘 직접 활용
다중 패턴 동시 탐색                   →  아호-코라식 (Aho-Corasick)
접두사 쿼리 다수                      →  트라이 (Trie)

📢 섹션 요약 비유: Z 알고리즘과 KMP는 같은 목적의 두 가지 여행 경로—Z 배열은 "출발지에서 얼마나 같은가"를 직접 기록하고, KMP 실패 함수는 "실패했을 때 어디로 돌아가야 하는가"를 기록한다.

Ⅴ. 기대효과 및 결론

Z 알고리즘은 Z-box 재활용으로 O(n) 시간 복잡도를 달성하여 KMP와 동등한 패턴 매칭 성능을 제공한다. 구현이 직관적이고 주기 탐색·문자열 분석에 직접 활용 가능하다는 장점이 있다. 다중 패턴 동시 매칭이 필요하면 아호-코라식, 임의 부분 문자열 탐색이면 서픽스 배열로 확장한다.

결론: 단일 패턴 매칭과 문자열 주기 분석에서 Z 알고리즘은 O(n+m)의 최적 복잡도를 제공하며, KMP보다 구현이 단순하여 실전에서 선호되는 경우가 많다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[:---]
    │
    ▼
[KMP 알고리즘]
    │
    ▼
[아호-코라식 (Aho-Corasick)]
    │
    ▼
[서픽스 배열 (Suffix Array)]
    │
    ▼
[Z-box]
    │
    ▼
[주기 탐색 (Period Finding)]
    │
    ▼
[트라이 (Trie)]

이 흐름도는 :---에서 출발해 주기 탐색 (Period Finding)까지 이어지며, 중간 단계가 기초 개념을 실무 구조로 발전시키는 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

1. Z 배열은 문자열의 각 위치에서 "여기서 시작하는 단어가 맨 앞과 몇 글자 같아?"를 기록한 표야.
2. "aabxaa"에서 Z[4]=4는 4번 위치 "aabx..."가 맨 앞 "aabx..."와 4글자 일치한다는 뜻이야.
3. 이 표 하나만 있으면 패턴이 어디 등장하는지, 가장 짧은 반복 단위가 뭔지 한 번에 알 수 있어!