Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기

알고리즘

Z 알고리즘

Z 알고리즘이란 문자열 관련 알고리즘으로, Z array를 채우는 알고리즘이다. 길이 N의 문자열 S가 주어졌을 때 Z array는 아래와 같이 정의된다.

Z[i]:=SS[i,N1]에 대해 longest common prefix의 길이

이를 O(N)에 구할 수 있다.

 

알고리즘은 KMP와 SA의 중간 정도 느낌이다.

i=1,...,N1에 대해 Z[i]를 차례로 구할 것이다. 이때 이전까지 구한 Z[i]에 대해, i+Z[i]가 최대인 경우의 양 끝점을 기억해두자. (L=i,R=i+Z[i]1)

i) R<i

그냥 naive하게 계산하자. 이후 LR 갱신.

ii) iR

자명하게 L<i이다. S[0,RL]S[L,R]이 일치한다는 점을 이용하자. Z[iL]Ri이면 Z[i]=Z[iL]이다. 만약 Z[iL]>Ri이면 Z[i]Ri+1이고, 여기서부터는 naive하게 계산해주면 된다. (이후 L,R도 갱신하기)

총 계산량이 R의 값이 증가한 양과 같기 때문에 O(N)이다.

 

아래 링크를 통해 공부하였다.

https://sgc109.tistory.com/208

 

아래는 코드이다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

int N;
char S[MAXN];
int z[MAXN];

void get_z() {
	z[0] = N;	// 그냥 의미상 N
	int L = 0, R = 0;
	for(int i = 1; i < N; i++) {
		if(R < i) {
			for(z[i] = 0; S[z[i]] == S[i + z[i]]; z[i]++);
			L = i;
			R = i + z[i] - 1;
		}
		else {
			if(z[i - L] <= R - i) z[i] = z[i - L];
			else {
				for(z[i] = R - i + 1; S[z[i]] == S[i + z[i]]; z[i]++);
				L = i;
				R = i + z[i] - 1;
			}
		}
	}
}

 

'알고리즘' 카테고리의 다른 글