Z 알고리즘
Z 알고리즘은 문자열의 각 위치에서 전체 문자열의 접두사와 얼마나 길게 일치하는지 Z 배열을 선형 시간에 구한다 문자열 전처리·패턴 매칭 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·...
| 분류 | 알고리즘 · 문자열 전처리·패턴 매칭 |
|---|---|
| 목적 | 문자열의 각 위치에서 전체 문자열의 접두사와 얼마나 길게 일치하는지 Z 배열을 선형 시간에 구한다 |
| 처리 방식 | 이전에 계산한 일치 구간 [l,r)을 재활용해 비교를 줄이고, 현재 위치가 구간을 벗어나면 직접 문자를 비교한다 |
| 복잡도·성능 | 문자열 길이 n에 대해 O(n) 시간, O(n) 공간 |
| 필수 조건 | 문자 비교와 경계·구분자의 안전한 처리가 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
Z 알고리즘은 문자열의 각 위치에서 전체 문자열의 접두사와 얼마나 길게 일치하는지 Z 배열을 선형 시간에 구한다 문자열 전처리·패턴 매칭 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 이전에 계산한 일치 구간 [l,r)을 재활용해 비교를 줄이고, 현재 위치가 구간을 벗어나면 직접 문자를 비교한다. 패턴과 구분자·텍스트를 연결하면 패턴 검색으로 응용할 수 있다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 문자열 길이 n에 대해 O(n) 시간, O(n) 공간 올바르게 적용하려면 문자 비교와 경계·구분자의 안전한 처리가 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 접두사 일치, 문자열 주기 및 정확한 패턴 검색에 사용한다. KMP의 접두사 함수와 다른 형태의 같은 문자열 구조 정보를 제공한다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]