Z-Algorithm

Z-algorithm menghitung Z-array dari sebuah string S dengan panjang n, di mana Z[i] menyimpan panjang substring terpanjang yang dimulai dari indeks i dan sekaligus menjadi prefix dari S. Sekali Z-array dibangun dalam O(n), kita langsung bisa menjawab banyak pertanyaan: lokasi pattern di text, deteksi periode string, longest common prefix antar suffix, hingga pencarian palindromik. Pada Chapter ini kita akan membangun Z-array dengan teknik Z-box (segmen kanan terjauh), memvisualisasikannya, dan memakainya untuk pattern matching dengan trik P + '#' + T.

Aturan: Z-Function #

Definisi formal: Z[i] = k terbesar sehingga S[i..i+k-1] == S[0..k-1]. Khusus Z[0] biasanya di-set 0 atau n (tidak dipakai untuk komputasi). Substring yang dimaksud adalah proper prefix — yaitu tidak boleh merupakan seluruh string itu sendiri.

Contoh: S = "aabxaabxcaabxaabxay".

text
i : 0 1 2 3 4 5 6 7 8 9 ...
S : a a b x a a b x c a ...
Z : 0 1 0 0 4 1 0 0 0 8 ...

Z[4] = 4: substring mulai indeks 4 adalah "aabx" yang juga merupakan prefix S[0..3].
Z[9] = 8: substring "aabxaabx" cocok dengan prefix "aabxaabx".

Mekanisme: Z-Box untuk Linearitas #

Ide utama Z-algorithm: simpan Z-box terkanan [l, r), yaitu segmen yang sudah dipetakan ke prefix. Saat menghitung Z[i]:

Bila i < r: kita tahu S[i..r-1] == S[i-l..r-l-1] (karena [l,r) adalah salinan prefix). Maka Z[i] ≥ min(r - i, Z[i - l]).
Selanjutnya, coba perpanjang secara eksplisit karakter per karakter hingga mismatch atau habis.
Bila i + Z[i] > r: perbarui Z-box ke [i, i + Z[i]).

flowchart LR subgraph Prefix A0["S[0..Z[i-l]-1]"] end subgraph Z-box l,r AL["S[l..r-1]"] AI["S[i..r-1]"] end A0 -.copy.-> AL A0 -.copy.-> AI

Karena r hanya monoton naik, total perpanjangan karakter dibatasi n → algoritma O(n).

Kode: Z-Function #

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<int> z_function(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> z(n, 0);
    int l = 0, r = 0;  // Z-box [l, r) dengan r maksimum
    for (int i = 1; i < n; ++i) {
        if (i < r) {
            z[i] = std::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;
}

int main() {
    std::string s = "aabxaabxcaabxaabxay";
    std::vector<int> z = z_function(s);
    std::cout << "s : " << s << '\n';
    std::cout << "i : ";
    for (int i = 0; i < static_cast<int>(s.size()); ++i) std::cout << i % 10;
    std::cout << "\nZ : ";
    for (int v : z) std::cout << v << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text
s : aabxaabxcaabxaabxay
i : 0123456789012345678
Z : 0 1 0 0 4 1 0 0 0 8 1 0 0 5 1 0 0 1 0 

int l = 0, r = 0;: inisialisasi Z-box kosong. r selalu menunjukkan batas kanan eksklusif segmen yang sudah dipetakan ke prefix.
if (i < r) z[i] = std::min(r - i, z[i - l]);: gunakan informasi Z-box. Bila z[i-l] < r - i, tidak bisa diperpanjang (akan mismatch sebelum r). Bila z[i-l] >= r - i, kita hanya tahu cocok hingga r - i karakter — sisanya belum diverifikasi.
while (... s[z[i]] == s[i + z[i]]) ++z[i];: perpanjang secara eksplisit. Karena r monoton naik, total iterasi while di seluruh loop adalah O(n).
if (i + z[i] > r): perbarui Z-box bila segmen baru lebih jauh ke kanan.
Hasil: cocok dengan analisis manual. Z[4] = 4 (substring "aabx"), Z[9] = 8 ("aabxaabx"), Z[13] = 5 ("aabxa").

Pattern Matching dengan Z-Function #

Triks klasik: gabungkan P + '#' + T di mana # adalah karakter yang tidak muncul di P maupun T. Hitung Z-array. Setiap Z[i] = m (panjang pattern) untuk i > m menandakan occurrence di indeks i - m - 1 pada T.

Mengapa pemisah # diperlukan? Tanpa pemisah, Z-box bisa “bocor” dari P ke T memberi nilai Z palsu. Pemisah memutus kemungkinan perpanjangan Z-box melintasi batas P/T.

cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<int> z_function(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i < r) z[i] = std::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;
}

std::vector<int> z_search(const std::string& T, const std::string& P) {
    std::string combined = P + '\1' + T;  // pemisah < karakter alfabet
    std::vector<int> z = z_function(combined);
    int m = static_cast<int>(P.size());
    std::vector<int> result;
    for (int i = m + 1; i < static_cast<int>(z.size()); ++i) {
        if (z[i] == m) result.push_back(i - m - 1);
    }
    return result;
}

int main() {
    std::string P = "aabx";
    std::string T = "aabxaabxcaabxaabxay";
    auto occ = z_search(T, P);
    std::cout << "P = " << P << '\n';
    std::cout << "T = " << T << '\n';
    std::cout << "Indeks: ";
    for (int idx : occ) std::cout << idx << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text
P = aabx
T = aabxaabxcaabxaabxay
Indeks: 0 4 9 13 

P + '\1' + T: gabungkan dengan pemisah '\1' (karakter ASCII 1, tidak muncul di teks biasa). Bisa juga '$', '#', dll. asalkan tidak ada di input.
z_function(combined): bangun Z-array sepanjang m + 1 + n. Pemisah memutus Z-box sehingga Z di area T tidak bisa “lari” kembali ke P.
if (z[i] == m): setiap i > m dengan Z[i] == m menandakan ke-4 karakter pattern cocok di posisi tersebut.
i - m - 1: konversi indeks dari string gabungan ke indeks asli di T. Indeks i = m + 1 + shift di string gabungan ↔ shift di T.
Empat indeks: 0, 4, 9, 13 adalah awal kemunculan "aabx" di T. Verifikasi: T[0..3]="aabx", T[4..7]="aabx", T[9..12]="aabx", T[13..16]="aabx".

Kompleksitas #

Tahap	Waktu	Ruang
Z-function untuk `S` panjang `n`	`O(n)`	`O(n)`
Pattern matching `P` di `T`	`O(n + m)`	`O(n + m)`
Total search	`O(n + m)`	`O(n + m)`

Sama dengan KMP, tetapi implementasi Z-algorithm sering lebih singkat dan memudahkan analisis struktural string.

Aplikasi Lanjutan Z-Function #

1. Deteksi Periode String #

String S memiliki periode p (bila S[i] == S[i + p] untuk semua i < n - p) jika dan hanya jika Z[p] == n - p. Untuk S = "abcabcabc", Z[3] = 6 = 9 - 3 → periode 3.

2. Longest Repeated Substring #

Cari max(Z[i]) untuk i > 0. Misal S = "banana", Z = [0, 0, 1, 3, 0, 0]. Max Z[3] = 3 → substring "ana" muncul minimal 2 kali.

3. Pencarian Palindromik #

Untuk menemukan palindrom terpanjang berpusat di awal S, balik S jadi S^R, gabungkan S + '#' + S^R, hitung Z, lalu Z[i] di area S^R memberi panjang palindrom yang berpusat di awal S.

4. Compression Run-Length #

Z-array membantu deteksi unit berulang: bila Z[i] == n - i dan n % i == 0, string dapat dikompresi menjadi (n/i) × S[0..i-1].

Perbandingan Z vs KMP #

Aspek	KMP	Z-algorithm
Struktur bantu	Failure function `f[i]`	Z-array `Z[i]`
Makna nilai	Longest proper prefix = suffix dari `P[0..i]`	Longest common prefix antara `S` dan `S[i..]`
Build	`O(m)`	`O(n)`
Search	`O(n)`	`O(n + m)` dengan trik `P + '#' + T`
Analisis struktur string	Terbatas	Kaya (periode, LCP, palindrom)
Kompleksitas kode	Lebih panjang (loop while)	Lebih singkat

Ringkasan #

Z-array Z[i] menyimpan panjang longest substring mulai dari i yang juga prefix dari string.
Build O(n) dengan teknik Z-box [l, r) yang monoton naik.
Pattern matching: gabungkan P + '#' + T, cari Z[i] == m di area T.
Total kompleksitas O(n + m) — sama dengan KMP, dengan kode lebih singkat.
Aplikasi lanjutan: deteksi periode, longest repeated substring, analisis palindromik, string compression.
Lebih kaya informasi dibanding failure function KMP; cocok bila perlu analisis struktural string.