Suffix Array

Suffix array adalah struktur data string yang merepresentasikan semua suffix dari sebuah string S dalam urutan lexicographic. Dengan mengurutkan suffix sekali saja (O(n log n) build), kita mendapatkan akses O(m log n) ke pattern matching, O(1) ke LCP antar dua suffix berurutan, dan O(n) ke longest repeated substring. Struktur ini menjadi dasar banyak algoritma string lanjutan karena jauh lebih hemat memori dibanding suffix tree. Pada Chapter ini kita akan membangun suffix array dengan algoritma prefix doubling O(n log² n), memvisualisasikannya pada string "banana", dan menyentuh aplikasi utamanya: pattern search binary, longest repeated substring, dan dasar untuk LCP array (Chapter berikutnya).

Aturan: Urutkan Semua Suffix #

Suffix ke-i dari S panjang n adalah S[i..n-1]. Suffix array SA[0..n-1] adalah permutasi dari {0, 1, ..., n-1} sehingga suffix SA[0], SA[1], …, SA[n-1] terurut naik secara lexicographic.

Contoh: S = "banana" (n=6).

i	Suffix `S[i..]`
0	`banana`
1	`anana`
2	`nana`
3	`ana`
4	`na`
5	`a`

Urutkan lexicographically:

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

Jadi SA = [5, 3, 1, 0, 4, 2].

Mekanisme: Prefix Doubling #

Sortir semua suffix secara langsung butuh O(n² log n) karena perbandingan dua suffix bisa panjang O(n). Algoritma prefix doubling mengurangi biaya dengan menyortir berdasarkan prefix panjang 2^k secara berturut-turut.

K = 0: sort berdasarkan 1 karakter. Rank awal = kode ASCII karakter.
K = 1, 2, 3, …: sort berdasarkan 2 karakter berikutnya. Rank suffix i = (rank[i], rank[i + 2^(k-1)]) — gabungan rank prefix pertama dan prefix kedua yang sudah diketahui.
Berhenti ketika semua suffix memiliki rank unik (rank maksimum = n - 1).

Setelah log n iterasi, suffix terurut penuh. Setiap iterasi O(n log n) (sorting dengan comparator) → total O(n log² n). Dengan radix sort, bisa turun ke O(n log n).

flowchart LR S0["Sort 1 char"] --> R0["Rank awal = ASCII"] R0 --> S1["Sort 2 char (rank, rank+k)"] S1 --> R1["Rank 2-char"] R1 --> S2["Sort 4 char (rank, rank+2k)"] S2 --> R2["Rank 4-char"] R2 --> End["log n iterasi → SA"]

Kode: Build Suffix Array + LCP #

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

struct SuffixArray {
    int n;
    std::vector<int> sa;       // suffix array
    std::vector<int> rank_;   // rank_[i] = posisi suffix i di sa
    std::vector<int> lcp;     // lcp[i] = LCP(sa[i-1], sa[i])

    explicit SuffixArray(const std::string& s) {
        n = static_cast<int>(s.size());
        build_sa(s);
        build_lcp(s);
    }

    void build_sa(const std::string& s) {
        sa.resize(n);
        rank_.assign(n, 0);
        std::vector<int> tmp(n, 0);

        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;
        }
    }

    void build_lcp(const std::string& s) {
        lcp.assign(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;
        }
    }
};

int main() {
    std::string s = "banana";
    SuffixArray sa(s);

    std::cout << "s = " << s << '\n';
    std::cout << "i  SA[i] suffix        LCP[i]\n";
    for (int i = 0; i < sa.n; ++i) {
        std::cout << i << "  " << sa.sa[i] << "    "
                  << s.substr(sa.sa[i])
                  << std::string(15 - (sa.n - sa.sa[i]), ' ')
                  << sa.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

rank_[i] = (unsigned char)s[i];: rank awal = kode karakter. Untuk "banana", rank awal [98, 97, 110, 97, 110, 97].
for (int k = 1; k < n; k <<= 1): k = 1, 2, 4, 8, …; sortir berdasarkan prefix panjang 2k menggunakan rank prefix k.
auto cmp = [&](int a, int b) {...}: comparator membandingkan (rank_[a], rank_[a+k]) vs (rank_[b], rank_[b+k]). -1 untuk suffix yang lebih pendek dari k (dianggap “paling kecil”).
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(...) ? 1 : 0);: kompresi rank baru. Bila dua suffix berbeda, rank berbeda; bila sama (cmp false), rank sama.
if (rank_[sa[n - 1]] == n - 1) break;: bila semua suffix sudah punya rank unik, sortir selesai lebih awal.
build_lcp: algoritma Kasai — dijelaskan di Chapter LCP. Hasil lcp = [0, 1, 3, 0, 0, 2]:
- lcp[1] = 1: LCP(“a”, “ana”) = “a” (1 karakter).
- lcp[2] = 3: LCP(“ana”, “anana”) = “ana” (3 karakter).
- lcp[3] = 0: LCP(“anana”, “banana”) = 0 (karakter pertama berbeda).
- lcp[5] = 2: LCP(“na”, “nana”) = “na” (2 karakter).

Aplikasi 1: Pattern Search Binary #

Setelah suffix array terurut, cari pattern P panjang m dengan binary search:

cpp
int pattern_search(const std::string& s, const SuffixArray& sa, const std::string& P) {
    int lo = 0, hi = sa.n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (s.compare(sa.sa[mid], P.size(), P) < 0) lo = mid + 1;
        else hi = mid;
    }
    if (lo < sa.n && s.compare(sa.sa[lo], P.size(), P) == 0) return sa.sa[lo];
    return -1;
}

Kompleksitas: O(m log n) per query — efisien untuk banyak query terhadap text tetap.
Bila butuh semua occurrence: expand ke kiri dan kanan dari posisi binary search selama LCP ≥ m.

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

struct SuffixArray {
    int n;
    std::vector<int> sa, rank_, lcp;
    explicit SuffixArray(const std::string& s) {
        n = static_cast<int>(s.size());
        build_sa(s); build_lcp(s);
    }
    void build_sa(const std::string& s) {
        sa.resize(n); rank_.assign(n, 0);
        std::vector<int> tmp(n, 0);
        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;
        }
    }
    void build_lcp(const std::string& s) {
        lcp.assign(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;
        }
    }
};

int main() {
    std::string s = "banana";
    SuffixArray sa(s);

    std::string P = "ana";
    int lo = 0, hi = sa.n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (s.compare(sa.sa[mid], P.size(), P) < 0) lo = mid + 1;
        else hi = mid;
    }
    bool found = (lo < sa.n && s.compare(sa.sa[lo], P.size(), P) == 0);
    std::cout << "Pattern '" << P << "' "
              << (found ? "ditemukan di " : "tidak ditemukan")
              << (found ? std::to_string(sa.sa[lo]) : "") << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Pattern 'ana' ditemukan di 3

s.compare(sa.sa[mid], P.size(), P): bandingkan substring S[sa.sa[mid]..] sepanjang |P| dengan P. Mengembalikan negatif/0/positif.
Binary search lower bound: cari posisi terkecil di SA sehingga suffix ≥ P. Bila suffix sama persis dengan P → ditemukan.
Hasil 3: pattern "ana" muncul di indeks 3 ("banana"[3..5] = "ana"). Pattern muncul juga di indeks 1 ("banana"[1..3] = "ana"), tetapi binary search menemukan satu occurrence; untuk semua occurrence, expand ke kiri/kanan dengan LCP.

Aplikasi 2: Longest Repeated Substring #

Substring terpanjang yang muncul minimal 2 kali = max(LCP[i]) untuk i = 1..n-1. Untuk "banana", max LCP = 3 (LCP(“ana”, “anana”)) → "ana" adalah longest repeated substring.

Aplikasi 3: Longest Common Substring (Dua String) #

Gabungkan S + '#' + T + '$' (pemisah unik), bangun suffix array + LCP. Cari nilai LCP maksimum antara dua suffix yang berasal dari string berbeda (satu di S, satu di T). Kompleksitas O(n + m).

Kompleksitas #

Operasi	Waktu	Ruang
Build SA (prefix doubling)	`O(n log² n)`	`O(n)`
Build SA (radix sort / SA-IS)	`O(n log n)` atau `O(n)`	`O(n)`
Build LCP (Kasai)	`O(n)`	`O(n)`
Pattern search	`O(m log n)` per pattern	—
Longest repeated substring	`O(n)` setelah build	—
Longest common substring (S, T)	`O(	S

Perbandingan dengan Suffix Tree #

Aspek	Suffix Array	Suffix Tree
Memori	`O(n)` (4 byte/suffix)	`O(n)` tetapi konstanta besar (~20×)
Build	`O(n log n)` atau `O(n)`	`O(n)`
Pattern search	`O(m log n)`	`O(m)`
Cache friendliness	Tinggi (array linear)	Rendah (tree pointer)
Implementasi	Relatif mudah	Kompleks

Suffix array hampir selalu menggantikan suffix tree dalam praktik karena simplicity dan cache locality.

Variasi Implementasi #

Naive O(n² log n): sort suffix dengan string::compare penuh. Mudah untuk belajar, tidak praktis untuk n > 1000.
O(n log² n) dengan std::sort: implementasi di Chapter ini. Cukup untuk kompetisi.
O(n log n) dengan radix sort: lebih cepat untuk n ≥ 10^6.
SA-IS O(n): tercepat tetapi kompleks; hanya dibutuhkan untuk n sangat besar.

Ringkasan #

Suffix array SA adalah permutasi indeks suffix sehingga suffix terurut lexicographically.
Build prefix doubling O(n log² n) dengan std::sort, atau O(n log n) dengan radix sort, atau O(n) dengan SA-IS.
Aplikasi utama: pattern search binary O(m log n), longest repeated substring O(n), longest common substring O(n + m).
LCP array dibangun dengan Kasai algorithm O(n) — detail di Chapter berikutnya.
Suffix array hampir selalu lebih disukai daripada suffix tree karena memori kecil, cache friendly, dan implementasi sederhana.
Build SA memang tidak murah (O(n log² n) minimum praktis), tetapi menggantikan banyak query berulang terhadap text tetap — amortisasi sangat efisien untuk skenario banyak query.