Z-함수와 그 계산¶

길이가 $n$인 문자열 $s$가 주어졌다고 가정합시다. 이 문자열의 Z-함수는 길이가 $n$인 배열로, $i$번째 원소는 위치 $i$부터 시작하여 $s$의 처음 문자들과 일치하는 문자의 최대 개수와 같습니다.

다시 말해, $z[i]$는 $s$의 접두사이면서 동시에 $i$에서 시작하는 $s$의 접미사의 접두사이기도 한 가장 긴 문자열의 길이입니다.

참고. 이 글에서는 모호함을 피하기 위해 $0$-기반 인덱스를 가정합니다. 즉, $s$의 첫 번째 문자는 인덱스 $0$을 가지고 마지막 문자는 인덱스 $n-1$을 가집니다.

Z-함수의 첫 번째 원소인 $z[0]$은 일반적으로 잘 정의되지 않습니다. 이 글에서는 이 값을 0으로 가정합니다(다만 이는 알고리즘 구현에 아무런 영향을 주지 않습니다).

이 글에서는 Z-함수를 $O(n)$ 시간에 계산하는 알고리즘과 그 다양한 응용을 소개합니다.

예시¶

예를 들어, 여러 문자열에 대해 계산한 Z-함수의 값은 다음과 같습니다.

"aaaaa" - $[0, 4, 3, 2, 1]$
"aaabaab" - $[0, 2, 1, 0, 2, 1, 0]$
"abacaba" - $[0, 0, 1, 0, 3, 0, 1]$

단순한 알고리즘¶

형식적 정의는 다음과 같은 기초적인 $O(n^2)$ 구현으로 나타낼 수 있습니다.

vector<int> z_function_trivial(string s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
    }
    return z;
}

모든 위치 $i$를 순회하면서 각 위치마다 $z[i]$를 갱신하는데, $z[i] = 0$에서 시작하여 불일치를 발견하지 않는 한(그리고 줄의 끝에 도달하지 않는 한) 값을 증가시킵니다.

물론 이것은 효율적인 구현이 아닙니다. 이제 효율적인 구현을 구성하는 방법을 보이겠습니다.

Z-함수를 계산하는 효율적인 알고리즘¶

효율적인 알고리즘을 얻기 위해 $i = 1$부터 $n - 1$까지 차례로 $z[i]$의 값을 계산하되, 새 값을 계산할 때 이전에 계산한 값들을 최대한 활용하도록 하겠습니다.

간결함을 위해, $s$의 접두사와 일치하는 부분 문자열을 구간 일치라고 부릅시다. 예를 들어, 구하려는 Z-함수의 값 $z[i]$는 위치 $i$에서 시작하는(그리고 위치 $i + z[i] - 1$에서 끝나는) 구간 일치의 길이입니다.

이를 위해 가장 오른쪽에 있는 구간 일치의 $[l, r)$ 인덱스를 유지합니다. 즉, 발견된 모든 구간 중에서 가장 오른쪽에서 끝나는 구간을 유지합니다. 어떤 의미에서 인덱스 $r$은 알고리즘이 문자열 $s$를 탐색한 "경계"로 볼 수 있으며, 그 지점 너머는 아직 알려지지 않았습니다.

그러면 현재 인덱스(Z-함수의 다음 값을 계산해야 하는 인덱스)가 $i$일 때, 두 가지 경우 중 하나가 됩니다.

$i \geq r$ -- 현재 위치가 이미 처리한 영역의 바깥에 있는 경우입니다.

이 경우 단순한 알고리즘(즉, 값을 하나씩 비교하는 방법)으로 $z[i]$를 계산합니다. 마지막에 $z[i] > 0$이면 가장 오른쪽 구간의 인덱스를 갱신해야 한다는 점에 유의하십시오. 새로운 $r = i + z[i]$가 이전 $r$보다 낫다는 것이 보장되기 때문입니다.
$i < r$ -- 현재 위치가 현재 구간 일치 $[l, r)$ 내부에 있는 경우입니다.

이 경우 이미 계산된 Z-값들을 사용하여 $z[i]$의 값을 어떤 값으로 "초기화"할 수 있으며("0부터 시작하는 것"보다는 확실히 낫습니다), 경우에 따라서는 꽤 큰 값으로 초기화할 수도 있습니다.

이를 위해, 부분 문자열 $s[l \dots r)$과 $s[0 \dots r-l)$이 일치한다는 점에 주목합니다. 이는 $z[i]$의 초기 근삿값으로, 대응하는 구간 $s[0 \dots r-l)$에 대해 이미 계산된 값, 즉 $z[i-l]$을 사용할 수 있다는 뜻입니다.

그러나 $z[i-l]$ 값은 너무 클 수 있습니다: 위치 $i$에 적용하면 인덱스 $r$을 넘어설 수 있습니다. 이는 허용되지 않습니다. $r$의 오른쪽에 있는 문자들에 대해서는 아무것도 알지 못하기 때문입니다: 그 문자들은 필요한 문자들과 다를 수 있습니다.

다음은 비슷한 상황의 예시입니다:

$$ s = "aaaabaa" $$

마지막 위치($i = 6$)에 도달하면, 현재 일치 구간은 $[5, 7)$이 됩니다. 그러면 위치 $6$은 위치 $6 - 5 = 1$에 대응하며, 이 위치의 Z-함수 값은 $z[1] = 3$입니다. 당연히 $z[6]$을 $3$으로 초기화할 수는 없습니다. 그것은 완전히 잘못된 값입니다. 초기화할 수 있는 최댓값은 $1$입니다 -- 일치 구간 $[l, r)$의 인덱스 $r$을 넘어서지 않는 가장 큰 값이기 때문입니다.

따라서 $z[i]$의 초기 근삿값으로 다음 값을 안전하게 사용할 수 있습니다:

$$ z_0[i] = \min(r - i,\; z[i-l]) $$

$z[i]$를 $z_0[i]$로 초기화한 후에는 단순 알고리즘을 실행하여 $z[i]$를 증가시켜 봅니다 -- 일반적으로 경계 $r$ 이후에는 구간이 계속 일치할지 알 수 없기 때문입니다.

따라서 전체 알고리즘은 두 경우로 나뉘며, 두 경우는 $z[i]$의 초깃값만 다릅니다: 첫 번째 경우에는 0으로 가정하고, 두 번째 경우에는 앞서 계산된 값들로부터 (위의 식을 사용하여) 결정됩니다. 그 후에는 알고리즘의 두 분기 모두 단순 알고리즘의 구현으로 귀결되며, 이 단순 알고리즘은 초깃값을 지정한 직후에 시작됩니다.

알고리즘은 매우 간단합니다. 매 반복마다 단순 알고리즘을 실행하지만, 선형 시간에 동작하는 알고리즘을 얻었다는 점에서 상당한 진전을 이루었습니다. 실행 시간이 선형임은 뒤에서 증명하겠습니다.

구현¶

구현은 상당히 간결합니다:

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

이 구현에 대한 설명¶

전체 풀이는 길이 $n$인 배열, 즉 $s$의 Z-함수를 반환하는 함수로 주어집니다.

배열 $z$는 처음에 0으로 채워집니다. 현재 가장 오른쪽 일치 구간은 $[0; 0)$으로 가정합니다(즉, 어떤 $i$도 포함하지 않도록 일부러 작게 잡은 구간입니다).

$i = 1 \dots n - 1$에 대한 루프 안에서 먼저 초깃값 $z[i]$를 결정합니다. 이 값은 0으로 남거나 위의 공식으로 계산됩니다.

그 후 단순 알고리즘이 $z[i]$의 값을 가능한 한 크게 증가시키려 시도합니다.

마지막으로 필요하다면(즉, $i + z[i] > r$이라면) 가장 오른쪽 일치 구간 $[l, r)$을 갱신합니다.

알고리즘의 점근적 동작¶

위 알고리즘의 실행 시간이 문자열 길이에 대해 선형임을 증명하겠습니다 -- 즉, $O(n)$입니다.

증명은 매우 간단합니다.

나머지는 모두 상수 연산의 묶음이고 그 합은 $O(n)$이므로, 우리가 살펴볼 것은 중첩된 while 루프입니다.

while 루프의 각 반복이 일치 구간의 오른쪽 경계 $r$를 증가시킨다는 것을 보이겠습니다.

이를 위해 알고리즘의 두 분기를 모두 살펴보겠습니다:

$i \geq r$

이 경우 while 루프는 한 번도 반복하지 않거나($s[0] \ne s[i]$인 경우), 위치 $i$에서 시작하여 매번 한 문자씩 오른쪽으로 이동하며 몇 번 반복합니다. 그 후에는 오른쪽 경계 $r$이 반드시 갱신됩니다.

따라서 $i \geq r$일 때 while 루프의 각 반복은 새로운 $r$ 인덱스의 값을 증가시킨다는 것을 알 수 있습니다.
$i < r$

이 경우 $z[i]$를 위 공식으로 주어지는 특정 값 $z_0$으로 초기화합니다. 이 초깃값 $z_0$을 $r - i$ 값과 비교해 봅시다. 다음 세 가지 경우가 있습니다.
- $z_0 < r - i$
  
  이 경우에는 while 루프가 한 번도 반복되지 않음을 증명합니다.
  
  이는 예를 들어 귀류법으로 쉽게 증명할 수 있습니다. 만약 while 루프가 적어도 한 번 반복했다면, 초기 근삿값 $z[i] = z_0$이 부정확했다(실제 일치 길이보다 작았다)는 뜻이 됩니다. 그러나 $s[l \dots r)$과 $s[0 \dots r-l)$이 같으므로, 이는 $z[i-l]$이 잘못된 값(원래보다 작은 값)을 가지고 있다는 것을 의미하게 됩니다.
  
  따라서 $z[i-l]$은 올바른 값이고 $r - i$보다 작으므로, 이 값은 구하려는 값 $z[i]$와 일치합니다.
- $z_0 = r - i$
  
  이 경우 while 루프는 몇 번 반복할 수 있지만, 비교를 $s[r]$부터 시작하여 $[l, r)$ 구간 너머로 나아가게 되므로 각 반복은 $r$ 인덱스 값의 증가로 이어집니다.
- $z_0 > r - i$
  
  이 경우는 $z_0$의 정의에 의해 불가능합니다.

이렇게 하여 내부 루프의 각 반복이 $r$ 포인터를 오른쪽으로 전진시킨다는 것을 증명했습니다. $r$은 $n-1$보다 클 수 없으므로, 내부 루프는 $n-1$번보다 많이 반복하지 않습니다.

알고리즘의 나머지 부분은 자명하게 $O(n)$에 동작하므로, Z-함수를 계산하는 전체 알고리즘이 선형 시간에 동작함을 증명했습니다.

응용¶

이제 구체적인 문제에 Z-함수를 활용하는 몇 가지 방법을 살펴보겠습니다.

이 응용들은 접두사 함수의 응용과 대체로 유사합니다.

부분 문자열 검색¶

혼동을 피하기 위해 $t$를 텍스트 문자열, $p$를 패턴이라고 부르겠습니다. 문제는 다음과 같습니다. 텍스트 $t$ 안에서 패턴 $p$가 나타나는 모든 위치를 찾으십시오.

이 문제를 풀기 위해 새로운 문자열 $s = p + \diamond + t$를 만듭니다. 즉, $p$와 $t$를 이어 붙이되 가운데에 구분 문자 $\diamond$를 넣습니다($\diamond$는 문자열 $p$나 $t$ 어디에도 확실히 나타나지 않도록 선택합니다).

$s$에 대한 Z-함수를 계산합니다. 그런 다음 구간 $[0; \; \operatorname{length}(t) - 1]$에 속하는 모든 $i$에 대해, 대응하는 값 $k = z[i + \operatorname{length}(p) + 1]$을 살펴봅니다. $k$가 $\operatorname{length}(p)$와 같으면 $t$의 $i$번째 위치에 $p$가 한 번 나타나는 것이고, 그렇지 않으면 $t$의 $i$번째 위치에는 $p$가 나타나지 않습니다.

실행 시간(및 메모리 사용량)은 $O(\operatorname{length}(t) + \operatorname{length}(p))$입니다.

문자열에 포함된 서로 다른 부분 문자열의 개수¶

길이가 $n$인 문자열 $s$가 주어질 때, $s$의 서로 다른 부분 문자열의 개수를 세십시오.

이 문제는 반복적으로 풀겠습니다. 즉, 현재 서로 다른 부분 문자열의 개수를 알고 있을 때, $s$의 끝에 문자 하나를 추가한 후 이 개수를 다시 계산합니다.

이제 $k$를 $s$의 서로 다른 부분 문자열의 현재 개수라고 합시다. $s$에 새 문자 $c$를 덧붙입니다. 당연히 이 새 문자 $c$로 끝나는 새로운 부분 문자열이 생길 수 있습니다(즉, 이 문자로 끝나면서 아직 등장한 적 없는 모든 문자열입니다).

문자열 $t = s + c$를 잡고 이를 뒤집습니다(문자를 역순으로 씁니다). 이제 우리의 과제는 $t$의 접두사 중 $t$의 다른 어느 곳에서도 나타나지 않는 것이 몇 개인지 세는 것입니다. $t$의 Z-함수를 계산하고 그 최댓값 $z_{max}$를 구합시다. 당연히 길이가 $z_{max}$인 $t$의 접두사는 $t$의 중간 어딘가에서도 나타납니다. 더 짧은 접두사들도 나타나는 것이 분명합니다.

따라서 $s$에 문자 $c$를 덧붙일 때 새로 나타나는 부분 문자열의 개수는 $\operatorname{length}(t) - z_{max}$와 같음을 알 수 있습니다.

결과적으로 길이가 $n$인 문자열에 대해 이 풀이의 실행 시간은 $O(n^2)$입니다.

이와 정확히 같은 방법으로, 문자열의 맨 앞에 문자를 덧붙이는 경우와 문자를 (끝이나 맨 앞에서) 제거하는 경우에도 여전히 $O(n)$ 시간에 서로 다른 부분 문자열의 개수를 다시 계산할 수 있다는 점은 주목할 만합니다.

문자열 압축¶

길이가 $n$인 문자열 $s$가 주어집니다. 이 문자열의 가장 짧은 "압축" 표현을 찾으십시오. 즉, $s$를 $t$를 한 번 이상 이어 붙인 것으로 나타낼 수 있는 가장 짧은 문자열 $t$를 찾으십시오.

해법은 다음과 같습니다. $s$의 Z-함수를 계산하고, $i$가 $n$을 나누는 모든 $i$에 대해 루프를 돕니다. $i + z[i] = n$을 만족하는 첫 번째 $i$에서 멈춥니다. 그러면 문자열 $s$는 길이 $i$로 압축될 수 있습니다.

이 사실의 증명은 접두사 함수를 사용하는 풀이의 경우와 같습니다.