Longest Common Prefix

Setelah suffix array terbangun, struktur bantu berikutnya yang paling penting adalah LCP array — array sepanjang n di mana LCP[i] menyimpan panjang longest common prefix antara suffix SA[i] dan SA[i-1]. LCP array memungkinkan kita menjawab banyak pertanyaan string dalam waktu linear atau quasi-linear: longest repeated substring, jumlah substring unik, longest common substring lintas string, hingga pattern search yang lebih cepat. Algoritma Kasai membangun LCP array dalam O(n) — sebuah pencapaian elegan yang bergantung pada satu observasi kunci: LCP berikutnya setidaknya sama dengan LCP sebelumnya dikurangi satu. Pada Chapter ini kita akan memahami observasi Kasai, mengimplementasikannya, dan menerapkannya pada longest repeated substring serta count unique substrings.

Aturan: Definisi LCP Array #

Diberikan suffix array SA dari string S. LCP array didefinisikan:

text

LCP[0] = 0   (tidak ada suffix sebelumnya)
LCP[i] = |longest common prefix(S[SA[i-1]..], S[SA[i]..])|   untuk i >= 1

Karena suffix SA[i-1] dan SA[i] berdekatan dalam urutan lexicographic, LCP merefleksikan “kemiripan” dua suffix bertetangga.

Contoh: S = "banana", SA = [5, 3, 1, 0, 4, 2].

i	SA[i]	suffix	LCP[i]
0	5	`a`	0
1	3	`ana`	1
2	1	`anana`	3
3	0	`banana`	0
4	4	`na`	0
5	2	`nana`	2

LCP[2] = 3: suffix SA[1] = "ana" dan SA[2] = "anana" berbagi prefix "ana" sepanjang 3 karakter.
LCP[5] = 2: suffix SA[4] = "na" dan SA[5] = "nana" berbagi "na" sepanjang 2 karakter.

Mekanisme: Observasi Kasai #

Computing LCP secara naive butuh O(n²) (bandingkan setiap pasangan suffix karakter per karakter). Algoritma Kasai menggunakan observasi penting:

Bila LCP[rank[i]] = h (LCP antara suffix i dan predecessor di SA), maka LCP[rank[i+1]] ≥ h - 1.

Bukti intuisi: suffix i berbagi h karakter dengan predecessor j = SA[rank[i] - 1]. Hilangkan karakter pertama → suffix i+1 dan j+1 berbagi h-1 karakter. Karena SA terurut, suffix i+1 berada di posisi rank[i+1] dengan predecessor yang juga punya prefix sama (atau lebih panjang) dengan j+1. Maka LCP[rank[i+1]] ≥ h - 1.

Konsekuensi: variabel h hanya naik maksimal n kali (1 per iterasi i) dan turun maksimal n kali (kasai trick h--). Total operasi O(n).

flowchart TD I["Iterasi i, h = LCP saat ini"] --> R{"rank[i] == 0?"} R -- Ya --> H0["h = 0, skip"] --> Next R -- Tidak --> J["j = SA[rank[i]-1]"] J --> W["while s[i+h]==s[j+h]: h++"] W --> S["LCP[rank[i]] = h"] S --> H["if h > 0: h--"] H --> Next["i++"] Next --> I

Kode: Kasai Algorithm #

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

std::vector<int> build_sa(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> sa(n), rank_(n), tmp(n);
    for (int i = 0; i < n; ++i) { sa[i] = i; rank_[i] = (unsigned char)s[i]; }
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rank_[a] != rank_[b]) return rank_[a] < rank_[b];
            int ra = a + k < n ? rank_[a + k] : -1;
            int rb = b + k < n ? rank_[b + k] : -1;
            return ra < rb;
        };
        std::sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        rank_ = tmp;
        if (rank_[sa[n - 1]] == n - 1) break;
    }
    return sa;
}

std::vector<int> build_lcp_kasai(const std::string& s, const std::vector<int>& sa) {
    int n = static_cast<int>(s.size());
    std::vector<int> rank_(n);
    for (int i = 0; i < n; ++i) rank_[sa[i]] = i;

    std::vector<int> lcp(n, 0);
    int h = 0;
    for (int i = 0; i < n; ++i) {
        if (rank_[i] == 0) { h = 0; continue; }
        int j = sa[rank_[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[rank_[i]] = h;
        if (h > 0) --h;
    }
    return lcp;
}

int main() {
    std::string s = "banana";
    std::vector<int> sa = build_sa(s);
    std::vector<int> lcp = build_lcp_kasai(s, sa);

    std::cout << "s = " << s << '\n';
    std::cout << "i  SA[i] suffix        LCP[i]\n";
    for (int i = 0; i < static_cast<int>(sa.size()); ++i) {
        std::string suf = s.substr(sa[i]);
        std::cout << i << "  " << sa[i] << "    "
                  << suf
                  << std::string(15 - static_cast<int>(suf.size()), ' ')
                  << lcp[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
s = banana
i  SA[i] suffix        LCP[i]
0  5    a              0
1  3    ana            1
2  1    anana          3
3  0    banana         0
4  4    na             0
5  2    nana           2

for (int i = 0; i < n; ++i) rank_[sa[i]] = i;: bangun array rank kebalikan. rank_[i] = posisi suffix i di SA. Diperlukan untuk iterasi Kasai yang memproses suffix secara urutan asli (bukan urutan SA).
int h = 0;: variabel h melacak lower bound LCP saat ini. Awal 0.
if (rank_[i] == 0) { h = 0; continue; }: suffix pertama di SA tidak punya predecessor → LCP = 0.
int j = sa[rank_[i] - 1];: suffix predecessor di SA untuk suffix i.
while (... s[i + h] == s[j + h]) ++h;: perpanjang LCP eksplisit dimulai dari h (bukan 0). Inilah inti Kasai — h tidak pernah reset ke 0 kecuali rank 0.
lcp[rank_[i]] = h;: simpan LCP untuk posisi rank_[i] di array.
if (h > 0) --h;: kasai trick. LCP suffix i+1 minimal h - 1. Turunkan h sebanyak 1 untuk iterasi berikutnya.
Hasil: LCP = [0, 1, 3, 0, 0, 2] cocok dengan analisis manual.

Kompleksitas #

Tahap	Waktu	Ruang
Build SA (precondition)	`O(n log² n)` atau `O(n)`	`O(n)`
Build LCP (Kasai)	`O(n)`	`O(n)`

Bukti linearitas Kasai: variabel h dinaikkan paling banyak n kali di seluruh loop (maksimal 1 per iterasi), dan diturunkan paling banyak n kali (kasai trick --h). Total operasi while: O(n). Loop luar n iterasi. Total O(n).

Aplikasi 1: Longest Repeated Substring #

Substring terpanjang yang muncul minimal 2 kali di S:

cpp
int max_lcp = 0, max_idx = 0;
for (int i = 1; i < n; ++i) {
    if (lcp[i] > max_lcp) { max_lcp = lcp[i]; max_idx = i; }
}
std::string lrs = s.substr(sa[max_idx], max_lcp);

Kompleksitas O(n) setelah LCP dibangun.
Untuk "banana": max LCP = 3 (di i = 2) → LRS = "ana".

Aplikasi 2: Jumlah Substring Unik #

Total substring berbeda dari S:

text

count = n*(n+1)/2 - sum(LCP[i])   untuk i = 1..n-1

Penjelasan: total substring = n(n+1)/2 (jumlah suffix). Substring yang berulang (tidak unik) = sum(LCP) karena setiap LCP merepresentasikan prefix bersama dengan suffix predecessor. Substring unik = selisihnya.

Untuk "banana": total = 6·7/2 = 21, sum LCP = 1+3+0+0+2 = 6, unik = 15.

Aplikasi 3: Longest Common Substring (Dua String) #

Gabungkan S + '#' + T + '$'. Bangun SA + LCP. Cari max LCP[i] di mana SA[i-1] dan SA[i] berasal dari string berbeda (satu di S, satu di T). Pemisah unik mencegah LCP melintasi batas.

cpp
// Mark setiap suffix: 0 = dari S, 1 = dari T, -1 = separator
std::vector<int> origin(n_total, -1);
for (int i = 0; i < n_S; ++i) origin[i] = 0;
for (int i = n_S + 1; i < n_S + 1 + n_T; ++i) origin[i] = 1;

// Cari max LCP[i] dengan origin[SA[i-1]] != origin[SA[i]]
int best = 0;
for (int i = 1; i < n_total; ++i) {
    if (origin[sa[i - 1]] != origin[sa[i]] && lcp[i] > best) {
        best = lcp[i];
    }
}

Aplikasi 4: Pattern Search Dipercepat #

Bila mencari pattern P di SA, gunakan LCP untuk mempersempit range binary search. Kompleksitas O(m + log n) dengan LCP precomputed, lebih cepat dari O(m log n).

Tabel Aplikasi LCP #

Aplikasi	Kompleksitas (setelah SA+LCP)	Catatan
Longest repeated substring	`O(n)`	`max(LCP)`
Count unique substrings	`O(n)`	`n(n+1)/2 - sum(LCP)`
Longest common substring (2 string)	`O(n + m)`	max LCP cross-origin
Pattern search dipercepat	`O(m + log n)` per pattern	LCP mempersempit range
Number of distinct palindrome	`O(n)` + Manacher	Lebih kompleks
Lexicographically k-th substring	`O(n)`	Walk SA, kurangi LCP

Perbandingan dengan Pendekatan Lain #

Pendekatan	Build	LCP query	LRS	Count unique
Brute force	—	`O(n²)`	`O(n² log n)`	`O(n²)`
Trie semua suffix	`O(n²)`	`O(n²)`	`O(n²)`	`O(n²)`
Suffix tree	`O(n)`	`O(n)`	`O(n)`	`O(n)`
SA + Kasai LCP	`O(n log² n)`	`O(n)`	`O(n)`	`O(n)`

SA + Kasai memberi hampir semua keuntungan suffix tree dengan implementasi jauh lebih sederhana.

Ringkasan #

LCP array LCP[i] = panjang longest common prefix antara suffix SA[i-1] dan SA[i].
Algoritma Kasai membangun LCP dalam O(n) menggunakan observasi: bila LCP[rank[i]] = h, maka LCP[rank[i+1]] ≥ h - 1.
Implementasi: iterasi suffix dalam urutan asli, perpanjang LCP dari lower bound h, turunkan h sebanyak 1 per iterasi (kasai trick).
Aplikasi utama: longest repeated substring, count unique substrings, longest common substring antar string, pattern search dipercepat.
LCP array adalah komplementer dari suffix array — keduanya dibangun bersama untuk analisis string lengkap.
SA + Kasai menggantikan suffix tree dalam mayoritas skenario praktis dengan implementasi jauh lebih sederhana.