Z 알고리즘

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

$Z[i]:=S$와 $S[i, N - 1]$에 대해 longest common prefix의 길이

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

 

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

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

i) $R < i$

그냥 naive하게 계산하자. 이후 $L$과 $R$ 갱신.

ii) $i \le R$

자명하게 $L < i$이다. $S[0, R - L]$과 $S[L, R]$이 일치한다는 점을 이용하자. $Z[i-L]\le R-i$이면 $Z[i]=Z[i-L]$이다. 만약 $Z[i-L]>R-i$이면 $Z[i]\ge R-i+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;
			}
		}
	}
}