Z 알고리즘(Z Algorithm) 완벽 가이드: O(m+n) 문자열 패턴 검색

Z 알고리즘이란?

이 알고리즘은 계산 과정에서 Z 배열을 생성해야 하기 때문에 'Z 알고리즘'이라는 이름이 붙었습니다. Z 배열의 크기는 탐색 대상 텍스트의 길이와 동일하며, 각 위치의 문자에서 시작하여 만들 수 있는 가장 긴 부분 문자열의 길이, 즉 접두사와 일치하는 최대 길이를 저장하는 용도로 사용됩니다.

먼저 패턴과 주 텍스트를, 양쪽 어디에도 등장하지 않는 특수 기호 하나로 이어 붙입니다. 패턴을 P, 주 텍스트를 T라고 할 때 연결 결과는 P$T 형태가 됩니다(단, $는 P와 T에 포함되어 있지 않다고 가정합니다).

이 알고리즘의 시간 복잡도는 O(m+n)입니다. 여기서 m은 패턴의 길이, n은 주 문자열의 길이를 의미합니다.

동작 원리

연결된 문자열 S = P$T에 대해 Z 배열의 i번째 값 Z[i]는 "S의 i번째 문자에서 시작하는 부분 문자열과 S 전체의 접두사가 일치하는 최대 길이"를 뜻합니다. 특수 문자 $가 중간에 존재하기 때문에, 어떤 위치 i에서 Z[i]가 패턴의 길이와 정확히 같다면 해당 위치에서 텍스트 안에 패턴이 완전히 일치함을 의미합니다.

효율성을 위해 알고리즘은 [L, R] 범위의 윈도우(window)를 유지합니다. 이 윈도우는 이미 확인된 영역으로, S[L..R]이 S의 접두사와 일치하는 가장 오른쪽 구간입니다. 새로운 위치가 윈도우 안에 있으면 이전에 계산한 Z 값을 재활용하고, 윈도우 밖에 있으면 처음부터 비교를 진행합니다. 덕분에 전체 비교 횟수가 크게 줄어들어 선형 시간 O(m+n)이 보장됩니다.

입력과 출력

입력:
주 문자열: "ABAAABCDBBABCDDEBCABC", 패턴: "ABC"

출력:
패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

알고리즘

fillZArray(conStr, ZArray)

입력 − conStr은 패턴과 주 텍스트를 연결한 문자열이며, ZArray는 각 위치별 최장 일치 길이를 저장할 배열입니다.

출력 − 값이 채워진 ZArray

시작
   n := conStr의 길이
   windLeft := 0, windRight := 0

   for i := 1 to n, do
      if i > windRight, then
         windLeft := i, windRight := i
         while windRight < n AND conStr[windRight-windLeft] =
            conStr[windRight], do
            windRight를 1 증가
         done
         ZArray[i] := windRight – windLeft
         windRight를 1 감소
      else
         k := i – windLeft
         if ZArray[k] < windRight – i + 1, then
            ZArray[i] := ZArray[k]
         else
            windLeft := i
            while windRight < n AND conStr[windRight-windLeft] =
               conStr[windRight], do
                windRight를 1 증가
            done
            ZArray[i] := windRight – windLeft
            windRight를 1 감소
   done
종료

zAlgorithm(text, pattern)

입력 − 주 텍스트와 검색할 패턴

출력 − 패턴이 발견된 위치들

시작
   conStr = pattern + "$" + text 를 연결
   patLen := pattern의 길이
   len := conStr의 길이
   fillZArray(conStr, ZArray)

   for i := 0 to len – 1, do
      if ZArray[i] = patLen, then
         위치 i – patLen – 1 을 출력
   done
종료

C++ 구현 예제

#include<iostream>
using namespace std;

void fillZArray(string conStr, int zArr[]) {
   int n = conStr.size();
   int windLeft, windRight, k;
   windLeft = windRight = 0;     // 초기 윈도우 크기는 0

   for(int i = 1; i < n; i++) {
      if(i > windRight) {
         windLeft = windRight = i;    // 윈도우 크기는 0이지만 위치를 i로 설정
         while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) {
            windRight++;    // 윈도우의 오른쪽 경계를 확장
         }
         zArr[i] = windRight-windLeft;
         windRight--;
      }else {
         k = i-windLeft;
         if(zArr[k] < windRight-i+1)
            zArr[i] = zArr[k];   // k번째 값이 남은 구간보다 작을 경우
         else {
            windLeft = i;
            while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) {
               windRight++;
            }
            zArr[i] = windRight - windLeft;
            windRight--;
         }
      }
   }
}

void zAlgorithm(string mainString, string pattern, int array[], int *index) {
   string concatedStr = pattern + "$" + mainString;   // 특수 문자로 연결
   int patLen = pattern.size();
   int len = concatedStr.size();
   int zArr[len];
   fillZArray(concatedStr, zArr);

   for(int i = 0; i<len; i++) {
      if(zArr[i] == patLen) {
         (*index)++;
         array[(*index)] = i - patLen -1;
      }
   }
}

int main() {
   string mainString = "ABAAABCDBBABCDDEBCABC";
   string pattern = "ABC";
   int locArray[mainString.size()];
   int index = -1;
   zAlgorithm(mainString, pattern, locArray, &index);

   for(int i = 0; i <= index; i++) {
      cout << "패턴 발견 위치: " << locArray[i]<<endl;
   }
}

실행 결과

패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

마무리

Z 알고리즘은 단순 반복 비교에 의존하는 나이브 문자열 검색(O(m×n))과 달리, 한 번의 전처리로 Z 배열을 구축한 뒤 이를 재활용하기 때문에 대용량 텍스트에서도 빠른 성능을 보여줍니다. 이러한 특성 덕분에 텍스트 편집기의 검색 기능, 로그 분석, 바이오인포매틱스의 DNA 서열 매칭 등 다양한 분야에서 활용되고 있습니다.