String Algorithms Lanjutan

Chapter sebelumnya membahas suffix array: struktur data ringkas O(n) yang mengurutkan semua suffix secara lexicographic untuk mendukung pattern matching O(m log n) dan longest repeated substring O(n). Tetapi ada dua struktur data string yang lebih ekspresif: suffix tree (compacted trie, semua suffix dalam O(n) node) dan suffix automaton (DFA minimal yang menerima semua suffix). Keduanya dapat dibangun online dengan O(n) per karakter, dan keduanya mendukung operasi yang lebih kaya daripada suffix array — misalnya jumlah kemunculan setiap substring, atau longest common substring dari banyak string. Pada Chapter ini kita membedah suffix automaton secara penuh (kode C++ dapat diuji), memberikan overview suffix tree Ukkonen, dan memetakan perbandingan ketiganya untuk berbagai use case.

Aturan: Trie, Tree, dan Automaton #

Struktur	Definisi	Node	Build
Suffix trie	Trie berisi setiap suffix karakter per karakter	`O(n²)`	`O(n²)`
Suffix tree	Trie terkompresi (edge berbobot substring)	`O(n)`	`O(n)` (Ukkonen)
Suffix automaton	DFA minimal menerima semua suffix	`O(2n)`	`O(n)` (online)
Suffix array	Array indeks suffix terurut	`O(n)`	`O(n log n)` atau `O(n)`

Suffix trie adalah struktur paling naif: insert setiap suffix ke trie karakter per karakter. Jumlah node mencapai n(n+1)/2 — tidak praktis untuk n > 1000. Tetapi konsepnya membantu memahami suffix tree dan automaton.

Suffix tree mengompresi jalur linear pada trie menjadi edge tunggal dengan label substring. Jumlah node turun ke O(n).

Suffix automaton adalah pendekatan berbeda: bangun DFA minimal yang menerima semua suffix. State berbagi jalur untuk substring yang muncul di banyak suffix → O(2n) state paling banyak.

Mekanisme: Suffix Trie (Motivasi) #

Untuk memahami kenapa suffix tree dan automaton penting, mari lihat suffix trie naif. Untuk string S = "ababa":

Insert suffix "ababa" → 6 node baru.
Insert suffix "baba" → 5 node baru (dari root, ‘b’ belum ada).
Insert suffix "aba" → reuse prefix ‘a’ dari root, lalu ‘b’ sudah ada, lalu ‘a’ sudah ada → 0 node baru.
Insert "ba" → reuse ‘b’ dari root, lalu ‘a’ sudah ada → 0 node baru.
Insert "a" → reuse → 0 node baru.

Total node trie = 10 (1 root + 6 + 5 + 0 + 0 + 0). Bandingkan dengan worst case n(n+1)/2 + 1 = 16 untuk string tanpa shared prefix (mis. "abcde").

Kode: Suffix Trie (Motivasi) #

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

using namespace std;

struct SuffixTrie {
    struct Node {
        unordered_map<char, int> next;
        int start_index = -1;  // indeks suffix yang berakhir di node ini
    };
    vector<Node> nodes;

    SuffixTrie() { nodes.push_back({}); }

    void insert_suffix(const string& s, int from) {
        int v = 0;
        for (int i = from; i < (int)s.size(); ++i) {
            char c = s[i];
            if (!nodes[v].next.count(c)) {
                nodes.push_back({});
                nodes[v].next[c] = nodes.size() - 1;
            }
            v = nodes[v].next[c];
        }
        nodes[v].start_index = from;
    }

    void build(const string& s) {
        for (int i = 0; i < (int)s.size(); ++i) insert_suffix(s, i);
    }
};

int main() {
    string s = "ababa";
    SuffixTrie trie;
    trie.build(s);

    cout << "String: " << s << " (panjang " << s.size() << ")\n";
    cout << "Jumlah node suffix trie: " << trie.nodes.size() << '\n';
    cout << "Batas teoretis (n(n+1)/2 + 1): " << s.size() * (s.size() + 1) / 2 + 1 << '\n';

    cout << "\nSuffix yang berakhir di terminal node (start_index):\n";
    for (size_t i = 0; i < trie.nodes.size(); ++i) {
        if (trie.nodes[i].start_index != -1) {
            cout << "  node " << i << " -> suffix dari indeks "
                 << trie.nodes[i].start_index
                 << " (" << s.substr(trie.nodes[i].start_index) << ")\n";
        }
    }
    return 0;
}

Output yang Dihasilkan:

text
String: ababa (panjang 5)
Jumlah node suffix trie: 10
Batas teoretis (n(n+1)/2 + 1): 16

Suffix yang berakhir di terminal node (start_index):
  node 1 -> suffix dari indeks 4 (a)
  node 3 -> suffix dari indeks 2 (aba)
  node 5 -> suffix dari indeks 0 (ababa)
  node 7 -> suffix dari indeks 3 (ba)
  node 9 -> suffix dari indeks 1 (baba)

Bedah Kode Baris-per-Baris #

Node { unordered_map<char,int> next; int start_index; }: setiap node punya map transisi karakter → indeks child. start_index = -1 artinya node internal (tidak ada suffix yang berakhir di sana).
insert_suffix(s, from): traverse dari root, tambahkan edge untuk setiap karakter s[i] yang belum ada. Setelah loop, tandai start_index = from di node akhir.
build(s): panggil insert_suffix untuk setiap starting position i = 0..n-1. Total n iterasi, masing-masing O(n) → total O(n²).
10 node: dari 16 worst case — penghematan terjadi karena suffix-suffix yang berbagi prefix ("a", "aba", "ababa" semuanya mulai dengan 'a') menggunakan edge yang sama dari root.
5 terminal node: setiap suffix memiliki tepat satu terminal. Node 1, 3, 5, 7, 9 masing-masing menandai akhir suffix dari indeks 4, 2, 0, 3, 1 (urutan hash map internal, bukan urutan lexicographic).

Mekanisme: Suffix Automaton (Online Construction) #

Suffix automaton adalah DFA minimal yang menerima semua suffix dari S. Properti penting:

State merepresentasikan kelas ekuivalensi substring-substring yang memiliki himpunan end position (posisi di S di mana substring berakhir) yang sama.
link (suffix link): hubungan antar kelas — link[v] menunjuk ke state yang merepresentasikan suffix terpanjang dari kelas v yang berada di kelas berbeda.
len[v]: panjang substring terpanjang di kelas v.

Konstruksi online (tambahkan karakter satu per satu):

Buat state baru cur untuk prefix baru S[0..i].
Mulai dari last (state prefix S[0..i-1]), traverse suffix link ke atas. Tambahkan transisi c ke cur untuk setiap state yang belum punya transisi c.
Bila menemukan state p yang sudah punya transisi c ke q:
- Bila len[p] + 1 == len[q]: link[cur] = q.
- Bila tidak: clone state q menjadi clone dengan len[clone] = len[p] + 1. Redirect transisi c dari semua predecessor p' (di rantai suffix link) yang menuju q ke clone. Set link[q] = link[cur] = clone.

Setelah semua karakter diproses, jumlah state ≤ 2n - 1 dan jumlah transisi ≤ 3n - 4.

Kode: Suffix Automaton #

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

using namespace std;

struct SuffixAutomaton {
    struct State {
        int len, link;
        unordered_map<char, int> next;
    };
    vector<State> st;
    int last;

    SuffixAutomaton() {
        st.push_back({0, -1, {}});
        last = 0;
    }

    void extend(char c) {
        int cur = st.size();
        st.push_back({st[last].len + 1, 0, {}});
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }

    bool contains(const string& s) {
        int v = 0;
        for (char c : s) {
            if (!st[v].next.count(c)) return false;
            v = st[v].next[c];
        }
        return true;
    }
};

int main() {
    string S = "ababa";
    SuffixAutomaton sam;
    for (char c : S) sam.extend(c);

    cout << "String: " << S << '\n';
    cout << "Jumlah state: " << sam.st.size() << '\n';
    cout << "Batas teoretis (2n): " << 2 * S.size() << '\n';

    vector<string> queries = {"a", "ba", "aba", "baba", "ababa",
                              "abab", "bab", "abc", "ababaX"};
    cout << "Query substring:\n";
    for (auto& q : queries) {
        cout << "  '" << q << "': " << (sam.contains(q) ? "YA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
String: ababa
Jumlah state: 6
Batas teoretis (2n): 10
Query substring:
  'a': YA
  'ba': YA
  'aba': YA
  'baba': YA
  'ababa': YA
  'abab': YA
  'bab': YA
  'abc': TIDAK
  'ababaX': TIDAK

Bedah Kode Baris-per-Baris #

State { int len, link; unordered_map<char,int> next; }: setiap state punya panjang substring terpanjang di kelasnya, suffix link, dan transisi karakter.
extend(c): tambahkan karakter c ke automaton. Buat state cur untuk prefix baru.
while (p != -1 && !st[p].next.count(c)): traverse suffix link dari last. Untuk setiap state p yang belum punya transisi c, tambahkan p --c--> cur. Ini memastikan semua state yang merepresentasikan substring S[0..i-1] sekarang bisa di-extend dengan c.
if (p == -1): bila traverse sampai ke root tanpa menemukan state yang sudah punya c, artinya c belum pernah muncul sebelumnya → link[cur] = 0 (root).
if (st[p].len + 1 == st[q].len): bila state q yang sudah ada punya len tepat len[p] + 1, artinya tidak ada substring yang perlu dipisah → link[cur] = q.
Clone state: bila len[q] > len[p] + 1, berarti q merepresentasikan substring yang berasal dari kelas berbeda. Clone q ke clone dengan len = len[p] + 1, copy transisi, dan arahkan ulang semua transisi c dari predecessor yang menuju q ke clone. Set link[q] = link[cur] = clone.
contains(s): traverse dari state 0 mengikuti transisi c untuk setiap karakter s. Bila stuck, return false; bila selesai, return true. Kompleksitas O(|s|) per query.
6 state untuk "ababa" (n=5): jauh di bawah batas 2n = 10. String dengan struktur berulang seperti "ababa" sangat efisien karena banyak substring berbagi kelas end position.
Substring check: semua substring "a", "ba", "aba", "baba", "ababa", "abab", "bab" adalah substring dari "ababa". "abc" dan "ababaX" bukan → return false.

Ukkonen Algorithm: Suffix Tree dalam `O(n)` #

Suffix tree adalah trie terkompresi: edge berbobot substring alih-alih karakter tunggal. Untuk S = "ababa":

flowchart TD R(("root")) --> A["$"] R --> B["abab$"] R --> C["b$"] R --> D["bab$"] R --> E["ab$"]

(5 leaf untuk 5 suffix, edge berbagi prefix di-split secara implisit.)

Ukkonen algorithm membangun suffix tree dalam O(n) (untuk alphabet konstan) atau O(n log |Σ|) (alphabet umum). Tiga ide kunci:

Implicit suffix: bila suffix adalah prefix dari suffix lain, tidak perlu node eksplisit. Tambah sentinel '$' di akhir untuk memaksa semua suffix menjadi explicit.
Active point: titik (node, edge, offset) di mana algoritma sedang bekerja. Memungkinkan traversal cepat ke posisi berikutnya tanpa traverse ulang dari root.
Suffix link: setiap internal node punya link ke node yang merepresentasikan suffix terpanjangnya. Memungkinkan “lompat” langsung ke posisi suffix berikutnya tanpa traverse dari root.

Algoritma menambahkan karakter satu per satu (fase i = 1..n), dan di setiap fase menambahkan i suffix baru (iterasi j = 1..i). Dengan suffix link dan active point, total iterasi O(n).

Implementasi penuh Ukkonen ~200-300 baris C++ dengan edge compression via (start, end) reference. Untuk kompetisi, suffix tree jarang dipakai karena suffix array + LCP + RMQ bisa menjawab sebagian besar query dengan kode lebih pendek.

Perbandingan: Kapan Pakai Apa #

Struktur	Build	Memori	Pattern search	Counting substring	LCS multiple strings	Online build
Suffix trie	`O(n²)`	`O(n²)`	`O(m)`	`O(n²)` all	`O(n²)`	Ya
Suffix tree (Ukkonen)	`O(n)`	`O(n)` (konstan besar)	`O(m)`	`O(n)`	`O(n)`	Ya
Suffix automaton	`O(n)`	`O(2n)`	`O(m)`	`O(n)`	`O(n)`	Ya
Suffix array + LCP	`O(n log n)`	`O(n)`	`O(m log n)`	`O(n)`	`O(n)`	Tidak

Aturan praktis:

Pattern matching banyak query, string statis → suffix array (O(m log n) per query, kode pendek).
Substring counting dynamic → suffix automaton.
Longest common substring 2 string → suffix array + LCP (paling sederhana).
Longest common substring banyak string dengan struktur kompleks → suffix tree.
Online pattern matching → suffix automaton.

Aplikasi Lanjutan #

Hitung Kemunculan Setiap Substring #

Dengan suffix automaton, jumlah kemunculan substring yang berakhir di state v = jumlah kali state v atau keturunannya dikunjungi selama konstruksi. Lakukan topological sort by len, propagate count dari state dengan len besar ke link-nya. Kompleksitas O(n).

Longest Common Substring (Dua String) #

Bangun suffix automaton untuk S, lalu traverse dengan T. Di setiap posisi, catat panjang match maksimum (O(|T|)). Hasil = maksimum. Kompleksitas total O(|S| + |T|).

Palindromic Substring Terpanjang #

Bangun suffix automaton untuk S dan suffix automaton untuk reverse(S). Traverse paralel untuk menemukan palindrom terpanjang. Atau gunakan Manacher algorithm O(n) khusus untuk palindrom.

Ringkasan #

Suffix trie: struktur naif O(n²) node, dasar konseptual.
Suffix tree (Ukkonen O(n)): trie terkompresi, ekspresif tetapi kompleks implementasi.
Suffix automaton (O(n) online): DFA minimal yang menerima substring, state O(2n).
Suffix array + LCP (lihat Chapter sebelumnya): paling ringkas, kode terpendek, cukup untuk mayoritas kompetisi.
Pilih struktur berdasarkan kebutuhan: statis vs online, jumlah query, kompleksitas operasi.

Aturan: Trie, Tree, dan Automaton #

Mekanisme: Suffix Trie (Motivasi) #

Kode: Suffix Trie (Motivasi) #

Bedah Kode Baris-per-Baris #

Mekanisme: Suffix Automaton (Online Construction) #

Kode: Suffix Automaton #

Bedah Kode Baris-per-Baris #

Ukkonen Algorithm: Suffix Tree dalam O(n) #

Perbandingan: Kapan Pakai Apa #

Aplikasi Lanjutan #

Hitung Kemunculan Setiap Substring #

Longest Common Substring (Dua String) #

Palindromic Substring Terpanjang #

Ringkasan #

Ukkonen Algorithm: Suffix Tree dalam `O(n)` #