Z 함수

접두사 함수보다 이해하기 조금 더 쉬운 대안으로 Z 함수가 있습니다.

문자열 $s$의 Z 함수는 배열 $z$로 정의되며, $z_i$는 $i$번째 위치에서 시작하는 부분 문자열 중 $s$의 접두사와 같은 가장 긴 부분 문자열의 길이입니다.

나이브하게 구현하는 것은 훨씬 더 간단합니다:

vector<int> slow_z_function(string s) {
    int n = (int) s.size();
    vector<int> z(n, 0); // z[0] считается не определенным
    for (int i = 1; i < n; i++)
        // если мы не вышли за границу и следующие символы совпадают
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
    return z;
}

aaaaa
04321

abcdef
000000

abacabadaba
00103010301

Z 함수는 크누스-모리스-프랫 알고리즘에서 접두사 함수 대신 사용할 수 있습니다. 다만 이제 필요한 위치는 $|s|$에서 끝나는 것이 아니라 $|s|$에서 시작하게 됩니다. 이제 남은 것은 Z 함수를 $O(n)$에 구하는 방법을 익히는 것뿐입니다.

#빠르게 계산하는 방법

왼쪽에서 오른쪽으로 진행하면서 z-블록, 즉 지금까지 발견한 접두사와 같은 부분 문자열 중 가장 오른쪽에 있는 것을 저장하겠습니다. 그 경계를 양 끝을 포함하여 $l$과 $r$로 표기하겠습니다.

지금 $z_i$를 구하려 하고, 그 이전의 값은 모두 이미 구했다고 합시다. 새로운 $i$번째 문자는 z-블록의 오른쪽에 있거나 z-블록 안에 있을 수 있습니다.

• 오른쪽에 있다면, 단순히 나이브하게 전수 탐색으로 $z_i$(즉, $s_i$에서 시작하며 접두사와 같은 최대 구간)를 구하고, 이를 새로운 z-블록으로 지정합니다.
• $i$번째 원소가 z-블록 내부에 있다면, $z_{i-l}$ 값을 살펴보고 이를 이용하여 $z_i$를 0이 아닐 수도 있는 어떤 값으로 초기화할 수 있습니다. $z_{i-l}$이 $z$-블록의 오른쪽 경계보다 왼쪽에 있다면 $z_i = z_{i-l}$입니다. $z_i$는 이보다 더 클 수 없습니다. 경계에 닿는다면 그 값을 경계까지로 «잘라낸» 다음 1씩 증가시킵니다.

vector<int> z_function(string s) {
    int n = (int) s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        // если мы уже видели этот символ
        if (i <= r)
            // то мы можем попробовать его инициализировать z[i - l],
            // но не дальше правой границы: там мы уже ничего не знаем
            z[i] = min(r - i + 1, z[i - l]);
        // дальше каждое успешное увеличение z[i] сдвинет z-блок на единицу
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        // проверим, правее ли мы текущего z-блока
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }
    return z;
}

점근적 복잡도. 이 알고리즘에서 수행하는 동작의 횟수는 z-블록의 오른쪽 경계가 이동하는 횟수와 같으며, 이는 $O(n)$입니다.

#비교

전체적으로 Z 함수와 접두사 함수는 매우 비슷하지만, 크누스-모리스-프랫 알고리즘은 모든 고전적인 프로그래밍 교재에 실려 있는 반면, Z 함수는 어째서인지 올림피아드 프로그래머 말고는 아는 사람이 거의 없습니다.

접두사 함수에 대해 또 하나 알아 두어야 할 중요한 점은 이것이 온라인 알고리즘이라는 것입니다. 다음 문자를 읽기만 하면 곧바로 그 값을 알 수 있습니다.

연습 문제 1. 접두사 함수 배열이 주어집니다. 원래 문자열은 주어지지 않습니다. 이 문자열의 Z 함수를 $O(n)$에 계산하십시오.

연습 문제 2. Z 함수 배열이 주어집니다. 원래 문자열은 주어지지 않습니다. 이 문자열의 접두사 함수를 $O(n)$에 계산하십시오.