Belajar Data Structure - Suffix Array & Suffix Tree
Suffix array dan suffix tree adalah struktur data untuk pattern matching pada string. Di episode ini kalian memahami suffix array sebagai array terurut semua suffix dengan LCP array, suffix tree sebagai trie dari semua suffix, serta mempraktikkan implementasi suffix array sederhana dan perbandingan dengan KMP untuk substring search.
#Pendahuluan
Setelah di episode 22 kita memahami LRU dan LFU cache, pada episode ini kita mempelajari suffix array dan suffix tree — dua struktur data yang dirancang khusus untuk pattern matching dan substring search pada string. Keduanya memecahkan masalah yang sama dengan cara berbeda: suffix array menggunakan array terurut yang kompak, suffix tree menggunakan trie yang powerful tetapi memakan banyak memori.
Suffix array dan suffix tree bukan hanya untuk interview — mereka digunakan di search engine (full-text search), bioinformatika (DNA sequence analysis), dan deduplication. Memahami keduanya memberi kalian alat yang sangat kuat untuk memanipulasi string.
#Suffix Array
#Konsep
Suffix array adalah array dari semua suffix dari string yang diurutkan secara leksikografis, disertai dengan indeks awal masing-masing suffix.
Untuk string "banana":
| Index | Suffix |
|---|---|
| 5 | a |
| 3 | ana |
| 1 | anana |
| 0 | banana |
| 4 | na |
| 2 | nana |
Suffix array: [5, 3, 1, 0, 4, 2]
#LCP Array
LCP array (Longest Common Prefix) menyimpan panjang prefix terpanjang yang sama antara suffix berurutan dalam suffix array. Berguna untuk menemukan substring yang berulang.
#Implementasi Sederhana
def suffix_array_brute(s):
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort()
return [idx for _, idx in suffixes]
def lcp_array(s, sa):
n = len(s)
rank = [0] * n
lcp = [0] * n
for i in range(n):
rank[sa[i]] = i
k = 0
for i in range(n):
if rank[i] == 0:
k = 0
continue
j = sa[rank[i] - 1]
while i + k < n and j + k < n and s[i + k] == s[j + k]:
k += 1
lcp[rank[i]] = k
if k > 0:
k -= 1
return lcp
s = "banana"
sa = suffix_array_brute(s)
print("Suffix array:", sa)
print("LCP array:", lcp_array(s, sa))#Substring Search dengan Suffix Array
def search_in_sa(s, sa, pattern):
n = len(s)
m = len(pattern)
def compare(pos):
for i in range(m):
if pos + i >= n or s[pos + i] != pattern[i]:
return s[pos + i] < pattern[i] if pos + i < n else True
return False
left, right = 0, n
while left < right:
mid = (left + right) // 2
if compare(sa[mid]):
left = mid + 1
else:
right = mid
start = sa[left] if left < n else -1
if start != -1 and s[start:start + m] == pattern:
return start
return -1
print(search_in_sa(s, sa, "nan"))#Suffix Tree
#Konsep
Suffix tree adalah trie kompresi dari semua suffix string. Setiap edge berisi substring (bukan satu karakter), dan setiap leaf merepresentasikan satu suffix.
#Keunggulan
- Substring search: O(m) di mana m = panjang pattern
- Longest common substring: O(n) dengan mencari internal node terdalam
- Pattern counting: hitung kemunculan pattern dalam O(m)
#Kompleksitas
| Operasi | Suffix Array | Suffix Tree |
|---|---|---|
| Build | O(n log n) | O(n) |
| Space | O(n) | O(n) tapi overhead besar |
| Substring search | O(m log n) | O(m) |
| Longest common | O(n) | O(n) |
#Perbandingan dengan KMP
| Aspek | KMP | Suffix Array |
|---|---|---|
| Preprocessing | O(m) | O(n log n) |
| Search per pattern | O(n) | O(m log n) |
| Banyak pattern | O(k × n) | O(k × m log n) |
| Space | O(m) | O(n) |
Suffix array lebih baik ketika ada banyak pattern yang perlu dicari pada string yang sama — preprocessing dilakukan sekali, lalu setiap search cukup O(m log n).
#Aplikasi
- Full-text search: search engine indexing
- DNA sequence analysis: mencari motif genetik
- Longest common substring: deduplication
- Data compression: LZW dan LZ77
Note
Untuk string sangat panjang (jutaan karakter), suffix array lebih praktis dari suffix tree karena lebih hemat memori. Suffix tree membutuhkan pointer tambahan untuk setiap edge dan node internal.
#Penutup
Inti yang harus dibawa pulang:
- Suffix array: array terurut suffix + LCP array → substring search O(m log n).
- Suffix tree: trie kompresi dari suffix → substring search O(m) tetapi overhead memori.
- Suffix array lebih praktis untuk string panjang; suffix tree lebih cepat.
- Lebih baik dari KMP untuk banyak pattern pada string yang sama.
- Aplikasi: full-text search, DNA analysis, longest common substring.
Ini adalah episode terakhir di Fase 5: Struktur Lanjutan & Khusus. Di episode 24 selanjutnya kita memasuki Fase 6: Pemilihan, Optimasi & Produksi dengan membahas decision matrix — framework untuk memilih struktur data yang tepat berdasarkan access pattern, frequency, dan constraints. Kita akan menyelesaikan 5 coding problems berbeda dan mengidentifikasi DS optimal untuk tiap kasus!