91. Z Algorithm

Z 알고리즘(Z Algorithm)은 문자열의 각각의 접미사와 전체 문자열의 가장 긴 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 이것도 설명이 간단하지는 않은데, 다음과 같은 예시를 보면 이해하기 쉽다. 문자열 $s = \ ^\shortparallel \mathsf{ababcacababa}^\shortparallel$이고 $|s| = n$이라고 하자.

$k$	$s_k$로 시작하는 접미사	접미사와 전체 문자열의 가장 긴 공통 접두사	$z(k)$
$0$	$\mathsf{ababcacababa}$	$\mathsf{ababcacababa}$	$12$
$1$	$\mathsf{babcacababa}$	(없음)	$0$
$2$	$\mathsf{abcacababa}$	$\mathsf{ab}$	$2$
$3$	$\mathsf{bcacababa}$	(없음)	$0$
$4$	$\mathsf{cacababa}$	(없음)	$0$
$5$	$\mathsf{acababa}$	$\mathsf{a}$	$1$
$6$	$\mathsf{cababa}$	(없음)	$0$
$7$	$\mathsf{ababa}$	$\mathsf{abab}$	$4$
$8$	$\mathsf{baba}$	(없음)	$0$
$9$	$\mathsf{aba}$	$\mathsf{aba}$	$3$
$10$	$\mathsf{ba}$	(없음)	$0$
$11$	$\mathsf{a}$	$\mathsf{a}$	$1$

문자열 $s$의 각각의 접미사에 대해 그 접미사와 전체 문자열을 앞에서부터 비교하면 몇 글자가 일치하는지 구하고, 일치하는 글자의 수를 $z(k)$라고 하면 $z(k)$가 Z 알고리즘에서 구하는 값이 된다. 각각의 $z(k)$를 저장하는 배열은 보통 Z 배열(Z Array) 또는 Z 박스(Z Box)라고 한다.

---

각각의 $z(k)$를 일일히 구한다면 시간복잡도는 $O(n^2)$일 것이다. 이 시간복잡도라면 Manacher 알고리즘과 마찬가지로 특수한 형태의 문자열에 대해서는 성능이 떨어진다. Z 알고리즘은 이를 $\Theta(n)$ 시간에 수행한다. 이 알고리즘에서는 이전에 구한 접미사의 공통 접두사 중 가장 오른쪽에서 끝나는 것의 시작 위치와 끝 위치를 가리키는 변수 $l$과 $r$이 존재하고, 초기값은 모두 $0$이다. 이 상태에서 Z 배열을 채우는데, $s_0$으로 시작하는 접미사는 전체 문자열과 같기 때문에 $z(0)$은 별로 의미가 없고, $z(1)$부터 차례로 구할 것이다.

 

각각의 값 $z(i)$를 구할 때 나올 수 있는 경우는 두 가지이다.

• $i > r$인 경우, 이전에 구한 값들로부터 얻을 수 있는 정보가 없어서 문자를 하나씩 비교해서 $z(i)$를 구한다. 이후 $l = i, r = i + z(i) - 1$로 바뀐다.
• $i \le r$인 경우, $s[i, r] = s_[i-l, r-l]$임을 알 수 있다. 또한 $z(i-l)$은 이미 구했으므로 $z(i-l)$의 값을 확인한다. 만약 $z(i-l) \le r-i$인 경우 $z(i) = z(i-l)$이 되고, 그렇지 않은 경우 $s[i, r] = s[0, r-i]$이며 뒤쪽 문자들을 확인해서 $z(i)$의 값을 결정한다. 뒤쪽 문자들을 확인한 경우 $r$은 $i + z(i) - 1$로 바뀐다.

 

구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int l, r, z[100005];
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    z[0] = n;
    for(int i = 1; i < n; i++)
    {
        if(i <= r)z[i] = min(r - i, z[i - l]);
        for(;s[i + z[i]] == s[z[i]];)z[i]++;
        if(i > r)l = i;
        r = max(r, i + z[i] - 1);
    }
}

Z 알고리즘의 시간복잡도는 다음과 같이 계산할 수 있다.

반복 과정에서 $l$과 $r$의 값이 변할 경우 항상 증가하고, 두 값 모두 초기값이 $0$이고 가능한 최대값이 $n-1$이므로 $l$과 $r$은 최대 $n-1$번 증가한다. 또한 문자 하나를 비교할 때마다 $r$이 $1$씩 증가하므로 문자 비교는 최대 $n-1$번 발생한다. 따라서 시간복잡도는 $\Theta(n)$이다.

 

[연습문제]

 

BOJ 13713. 문자열과 쿼리 (Platinum V)

$s$를 뒤집은 다음 Z 배열을 채운다. 쿼리 처리 역시 뒤쪽을 기준으로 하면 된다.

 

CF 1537E2. Erase and Extend (Hard Version) (2200)

(Todo)

 

→ solved.ac tag: z