C++ Z 알고리즘 완벽 가이드: 선형 시간 O(m+n) 패턴 검색

Z 알고리즘이란?

Z 알고리즘(Z algorithm)은 문자열 안에서 특정 패턴이 나타나는 위치를 선형 시간에 찾아내는 문자열 검색 알고리즘입니다. 검색 대상 문자열의 길이가 n이고, 찾으려는 패턴의 길이가 m일 때, 전체 탐색에 걸리는 시간 복잡도는 O(m+n)으로 매우 효율적입니다.

이 알고리즘은 Z 배열이라는 특수한 배열을 활용해 패턴의 등장 위치를 빠르게 계산합니다.

Z 배열이란?

Z 배열은 검색 대상 문자열과 같은 길이를 가지는 배열입니다. 각 요소 Z[i]는 인덱스 i에서 시작하는 부분 문자열 중, 문자열 자체의 접두사(prefix)와 일치하는 가장 긴 부분 문자열의 길이를 의미합니다.

예를 들어 문자열이 "aabxaab"라면, 인덱스 3에서 시작하는 부분 문자열 "aab"는 문자열 전체의 접두사 "aab"와 일치하므로 Z[3] = 3이 됩니다.

알고리즘 동작 원리

길이 n인 문자열 S와 길이 m인 패턴 p가 주어졌다고 가정합니다. 먼저 Z 배열을 생성한 뒤, i = 1부터 n-1까지 문자열의 각 문자를 한 번씩 순회하면서 다음을 수행합니다.

순회 과정에서는 1 ≤ L ≤ i ≤ R을 만족하는 구간 [L, R]을 관리합니다. 이 구간은 인덱스 L부터 시작하는 부분 문자열이 문자열의 접두사와 일치함을 나타내며, 이전 단계(i-1까지)에서 계산된 Z 값들을 재활용해 불필요한 비교를 줄입니다.

i번째 위치에서 Z[i] 값과 새로운 구간 [L, R]은 아래 규칙에 따라 계산됩니다.

Step 1: 만약 i > R 이라면,
  더 이상 확장 가능한 접두사 부분 문자열이 없으므로 새로운 구간을 시작합니다.
  인덱스 0(문자열 시작)부터의 부분 문자열과 인덱스 i부터의 부분 문자열을
  직접 비교하며 일치하는 길이를 구하고, Z[i] = R - L + 1 로 계산합니다.

Step 2: 만약 i ≤ R 이라면,
  기존 구간 [L, R]을 i까지 확장해 활용할 수 있습니다.
  k = i - L 일 때, Z[i] ≥ min(Z[k], R - i + 1) 이 성립합니다.
    Step 2.1: Z[k] < R - i + 1 이면,
      더 긴 접두사 부분 문자열은 존재하지 않으므로 Z[i] = Z[k] 입니다.
    Step 2.2: Z[k] ≥ R - i + 1 이면,
      더 긴 부분 문자열이 존재할 수 있으므로 L = i 로 갱신하고,
      S[R+1]부터 추가로 일치 여부를 비교하며 R을 확장합니다.

이 과정을 통해 모든 Z 값을 단 한 번의 순회만으로 계산할 수 있으며, 이것이 Z 알고리즘이 선형 시간에 동작하는 핵심 이유입니다.

C++ 구현 예제

패턴과 텍스트를 "$" 구분자로 연결한 하나의 문자열을 만들어 Z 배열을 계산하면, Z[i] 값이 패턴의 길이와 같아지는 지점이 곧 패턴이 등장하는 위치가 됩니다.

#include<iostream>
using namespace std;
void createZarray(string str, int Z[]){
   int n = str.length();
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i){
      if (i > R){
         L = R = i;
         while (R<n && str[R-L] == str[R])
         R++;
         Z[i] = R-L;
         R--;
      } else {
         k = i-L;
         if (Z[k] < R-i+1)
            Z[i] = Z[k];
         else {
            L = i;
            while (R<n && str[R-L] == str[R])
               R++;
            Z[i] = R-L;
            R--;
         }
      }
   }
}
void zAlgorithm(string text, string pattern){
   string str = pattern+"$"+text;
   int len = str.length();
   int Z[len];
   createZarray(str, Z);
   for (int i = 0; i < len; ++i){
      if (Z[i] == pattern.length())
         cout<<(i-pattern.length()-1)<<"\t";
   }
}
int main(){
   string str = "Hello! Welcome To tutorials Point programming tutorial";
   string pattern = "tutorial";
   cout<<"The patter ' "<<pattern<<" ' is found in the string '"<<str<<" ' at index \t";
   zAlgorithm(str, pattern);
   return 0;
}

실행 결과

The patter ' tutorial ' is found in the string 'Hello! Welcome To tutorials Point programming tutorial ' at index 18 46

위 결과에서 패턴 "tutorial"은 텍스트 내 인덱스 18("tutorials")과 인덱스 46("tutorial") 두 곳에서 발견되었습니다. 이처럼 Z 알고리즘은 KMP 알고리즘과 함께 대표적인 선형 시간 문자열 검색 기법으로, 텍스트 편집기의 찾기 기능이나 DNA 서열 분석 등 다양한 분야에서 활용됩니다.