Z 알고리즘

Z 알고리즘

문자열의 각 위치 i에서 시작하는 부분 문자열과 전체 문자열의 최장 공통 접두사 길이(Z[i])를 O(n) 시간에 계산하는 알고리즘으로, 문자열 매칭과 패턴 검색에 활용

목적: 접두사 매칭, 문자열 검색, 선형 시간 패턴 매칭

특징: 선형 시간(O(n)), Z 배열, 이전 정보 재활용

Z 배열: Z[i] = 문자열 S[0..]과 S[i..]의 최장 공통 접두사 길이, Z[0]은 정의 안함 또는 n

핵심 아이디어: [L, R] 구간 유지(R이 가장 오른쪽인 Z-box), Z[i]를 계산할 때 Z[i-L] 정보 재활용

동작: ① L=0, R=0 초기화 → ② i=1부터 n-1까지 → ③ i > R이면 직접 비교, i ≤ R이면 Z[i-L] 활용 → ④ 확장 가능하면 확장 → ⑤ L, R 갱신

문자열 매칭: 패턴 P와 텍스트 T를 P$T (구분자 사용)로 결합 → Z 배열 계산 → Z[i] == |P|인 위치 찾기

시간 복잡도: O(n) - R은 단조 증가, 각 문자 최대 한 번 비교

공간 복잡도: O(n) - Z 배열

장점: 선형 시간(O(n)), 단순 구현(KMP보다), 다양한 응용

단점: 추가 메모리(Z 배열), 패턴 매칭 외 활용 제한적

적용사례: 패턴 매칭, 문자열 접두사 분석, 반복 패턴 찾기, 알고리즘 대회

비교: Z(O(n)/단순) vs KMP(O(n+m)/실패함수) vs Boyer-Moore(평균빠름/복잡)

연관: 문자열 매칭, KMP, 접두사, 패턴 검색