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≤R
자명하게 L<i이다. S[0,R−L]과 S[L,R]이 일치한다는 점을 이용하자. Z[i−L]≤R−i이면 Z[i]=Z[i−L]이다. 만약 Z[i−L]>R−i이면 Z[i]≥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;
}
}
}
}
'알고리즘' 카테고리의 다른 글
FWHT (Fast Walsh-Hadamard Transform) (1) | 2021.10.05 |
---|---|
아호코라식 (Aho-Corasick) (0) | 2021.08.21 |
MCMF (Minimum Cost Maximum Flow) (0) | 2021.06.23 |
SPFA (Shortest Path Faster Algorithm) (0) | 2021.06.23 |
FFT (Fast Fourier Transform) (0) | 2021.04.03 |