Z 알고리즘 (Z Algorithm)

정의

Z 알고리즘 (Z Algorithm) 은 문자열 s[0..N-1] 의 각 위치 i 에 대해, s[i..] 와 s[0..] 의 최장 공통 접두사 (LCP) 길이 를 O(N) 시간에 모두 계산하는 선형 알고리즘.

결과 배열 Z[i] 는:

Z[i] = max { k : s[0..k-1] == s[i..i+k-1] }
Z[0] 은 정의되지 않거나 N (전체 길이)

KMP 와 비슷한 역할 (패턴 매칭 O(N+M)) 이지만, 구현이 더 직관적이고 짧아서 대회에서 선호됨.

문제 상황과 동기

길이 M 패턴 P 를 길이 N 텍스트 S 에서 찾는다.

• naive: 모든 위치 i 에서 P 와 S[i..] 를 비교. O(N·M).
• KMP: O(N+M), 하지만 failure function 구현이 복잡.
• Z 알고리즘: s = P + '$' + S (delimiter) 로 합친 후 Z 배열 계산. Z[i] == M 인 i 가 매칭 위치. O(N+M), 코드 ~20줄.

핵심 통찰: 이미 매칭된 구간 (Z-box) 을 최대한 재사용. amortized O(N).

시각화

핵심 아이디어

Z-box: 위치 i 까지 계산할 때, [l, r] 구간은 “가장 오른쪽으로 뻗은 매칭 구간” (s[l..r] == s[0..r-l]).

invariant: r = max { i + Z[i] - 1 } (지금까지)

새 i 계산:

1. i > r: naive 비교 시작, Z[i] 갱신, (l, r) 갱신.
2. i ≤ r: s[i..r] 는 s[i-l..r-l] 와 일치 (Z-box 내부). Z[i-l] 을 재사용:
   • Z[i-l] < r - i + 1: Z[i] = Z[i-l] (재사용 가능)
   • Z[i-l] ≥ r - i + 1: r 너머 확장 시도 필요, naive 비교로 연장

amortized O(N): r 은 최대 N-1 까지 증가, 한 번 증가하면 다시 감소 안 함. 총 비교 횟수 O(N).

알고리즘

z_function(s):
    N = len(s)
    Z = [0] * N
    l, r = 0, 0
    for i = 1 to N-1:
        if i > r:
            k = 0
            while i + k < N and s[k] == s[i + k]:
                k++
            Z[i] = k
            if k > 0:
                l, r = i, i + k - 1
        else:
            k = i - l
            if Z[k] < r - i + 1:
                Z[i] = Z[k]
            else:
                k = r - i + 1
                while i + k < N and s[k] == s[i + k]:
                    k++
                Z[i] = k
                l, r = i, i + k - 1
    return Z

구현

// Z algorithm: O(N) LCP of s[i..] and s[0..]
#include <bits/stdc++.h>
using namespace std;
vector<int> z_function(const string& s) {
  int n = s.size();
  vector<int> z(n);
  int l = 0, r = 0;
  for (int i = 1; i < n; i++) {
      if (i > r) {
          l = r = i;
          while (r < n && s[r - l] == s[r]) r++;
          z[i] = r - l; r--;
      } else {
          int k = i - l;
          if (z[k] < r - i + 1) z[i] = z[k];
          else {
              l = i;
              while (r < n && s[r - l] == s[r]) r++;
              z[i] = r - l; r--;
          }
      }
  }
  return z;
}
int main() {
  string s; cin >> s;
  auto z = z_function(s);
  for (int i = 1; i < (int)s.size(); i++)
      cout << z[i] << (i + 1 == s.size() ? "\n" : " ");
}

# Z algorithm in Python (O(N))
def z_function(s):
  n = len(s)
  z = [0] * n
  l, r = 0, 0
  for i in range(1, n):
      if i > r:
          l = r = i
          while r < n and s[r - l] == s[r]:
              r += 1
          z[i] = r - l
          r -= 1
      else:
          k = i - l
          if z[k] < r - i + 1:
              z[i] = z[k]
          else:
              l = i
              while r < n and s[r - l] == s[r]:
                  r += 1
              z[i] = r - l
              r -= 1
  return z
​
s = input().strip()
z = z_function(s)
print(" ".join(map(str, z[1:])))

// Z function in Java
import java.util.*;
public class Main {
  static int[] zFunction(String s) {
      int n = s.length();
      int[] z = new int[n];
      int l = 0, r = 0;
      for (int i = 1; i < n; i++) {
          if (i > r) {
              l = r = i;
              while (r < n && s.charAt(r - l) == s.charAt(r)) r++;
              z[i] = r - l; r--;
          } else {
              int k = i - l;
              if (z[k] < r - i + 1) z[i] = z[k];
              else {
                  l = i;
                  while (r < n && s.charAt(r - l) == s.charAt(r)) r++;
                  z[i] = r - l; r--;
              }
          }
      }
      return z;
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String s = sc.next();
      int[] z = zFunction(s);
      for (int i = 1; i < s.length(); i++)
          System.out.print(z[i] + (i + 1 == s.length() ? "\n" : " "));
  }
}

aaabaab

2 1 0 2 1 0

abc$abcabc

0 0 0 0 3 0 0 3 0 0

복잡도

패턴 매칭 응용

길이 M 패턴 P, 길이 N 텍스트 S:

string s = P + "$" + S;  // '$' 는 P, S 어디에도 없는 delimiter
auto z = z_function(s);
for (int i = M + 1; i < (int)s.size(); i++) {
    if (z[i] == M) {
        // i - M - 1 이 S 에서의 매칭 시작 위치
    }
}

O(N+M) 시간, O(N+M) 공간.

변형 / 활용

1. 최장 접두사 = 접미사

s + s 의 Z 배열에서 Z[i] + i == 2N 인 i 찾기. O(N).

2. 회문 판정

s + reverse(s) 의 Z 배열. 하지만 매내처 가 더 빠름.

3. 주기 찾기

Z[i] ≥ N - i 인 가장 작은 i. 문자열의 최소 주기 길이 i.

4. 다중 패턴 매칭

P1 + ’$’ + P2 + ’#’ + S 같은 방식으로 여러 패턴 동시 처리. 하지만 Aho-Corasick 이 더 효율적.

함정

1. Z[0] 정의

Z[0] 은 미정의 또는 N. 코드에 따라 0 또는 N. 보통 쓰지 않음.

2. delimiter 누락

패턴 매칭 시 P + S 로 합치면 P 끝과 S 시작이 이어져서 오판. 반드시 P + '$' + S 로 구분.

3. r < l 상태

r 이 i-1 보다 작을 때 i > r 조건 실패하면 l, r 갱신 안 되어 버그. 구현 정확히.

4. 중복 비교

while (r < n && s[r-l] == s[r]) r++ 루프가 amortized O(N) 임을 신뢰하지 못하고 불필요한 최적화 시도. 그대로 둬야 함.

KMP vs Z 알고리즘

대부분의 경우 Z 가 더 간단하므로 KMP 대신 Z 사용 권장.

BOJ 연습 문제

참고

• KMP 알고리즘 (failure function 기반 패턴 매칭)
• 문자열 해싱 (확률적 O(1) 비교)
• 매내처 알고리즘 (최장 회문 O(N))
• Aho-Corasick (다중 패턴 매칭 오토마타)