Permintaan dan kapan ini berlaku
Suffix array menyimpan indeks awal dari setiap sufiks, yang diurutkan secara leksikografis. Ketika satu teks tetap menerima banyak kueri pola, indeks ini menemukan kecocokan tanpa memindai ulang dari awal. Stanford CS166 meminta kandidat untuk mengimplementasikan searchFor, mengembalikan setiap kecocokan, dan memperhitungkan ukuran keluaran; di mana m adalah panjang pola, n adalah panjang teks, dan z adalah jumlah hasil.
Apa yang sedang diuji oleh pewawancara
- Menjelaskan bahwa kemunculan pola adalah sufiks yang prefiksnya sama dengan pola tersebut.
- Menemukan batas kiri dan kanan dengan batas bawah (lower bound), alih-alih berhenti pada satu kecocokan saja.
- Memisahkan biaya konstruksi satu kali dari biaya per kueri dan membebankan O(z) untuk keluaran.
- Menangani pola kosong, sentinel, sufiks duplikat, dan biaya perbandingan karakter.
Klarifikasi yang perlu ditanyakan terlebih dahulu
- Apakah teks bersifat tetap dan dikueri berkali-kali? Jika sering berubah, membangun kembali suffix array mungkin tidak cocok.
- Apakah jawabannya harus mengembalikan semua indeks awal, hanya jumlahnya, atau sekadar keberadaannya?
- Apakah kapitalisasi (case), normalisasi Unicode, dan pengurutan tingkat bita telah ditentukan? Pembanding harus sesuai dengan kontrak tersebut.
- Apakah suffix array sudah disediakan, atau harus dibangun? Jika pembuatan diperlukan, apakah pengurutan untuk tujuan pembelajaran dapat diterima atau diharapkan konstruksi waktu linier?
Jawaban 30 detik
"Sufiks-sufiks telah diurutkan, sehingga semua sufiks yang berawalan pattern membentuk satu interval yang berurutan. Saya membandingkan pola dengan text[sa[i]:] berdasarkan prefiks, menggunakan satu pencarian biner untuk sufiks pertama yang tidak lebih kecil dari pola tersebut dan pencarian biner lainnya untuk sufiks pertama yang benar-benar melampaui prefiks tersebut. Setiap nilai sa dalam interval tersebut adalah kecocokan, sehingga biaya pelaporan adalah O(z) dan kueri adalah O(m log n + z). Berdasarkan konvensi, pola kosong mengembalikan n+1 posisi."
Solusi langkah demi langkah
Langkah 1: Tentukan arti suffix array
Untuk banana, awal sufiks dalam urutan leksikografis adalah [5, 3, 1, 0, 4, 2]. Array ini menyimpan indeks awal bilangan bulat, bukan salinan string sufiks. Catatan MIT menjelaskan secara tepat indeks leksikografis ini dan penggunaan pencarian biner.
Langkah 2: Ubah pencocokan menjadi sebuah interval
Semua sufiks yang berawalan ana saling berdampingan, sehingga jawabannya adalah interval setengah terbuka [left, right). Pembanding membutuhkan tiga hasil: prefiks sufiks berada di bawah, sama dengan, atau di atas pola. Jika sama, pencarian harus tetap berlanjut ke kiri dan ke kanan untuk menangkap setiap kemunculan.
Langkah 3: Terapkan dua batas bawah (lower bound)
Batas bawah pertama mencari prefiks sufiks pertama yang tidak berada di bawah pola. Batas bawah kedua mencari prefiks sufiks pertama yang secara ketat berada di atasnya, atau menemukan ujung kanan dari rentang yang sama. Membandingkan pola dengan sufiks lengkap adalah keliru: sufiks yang lebih pendek yang merupakan prefiks dari pola harus dianggap lebih kecil.
Langkah 4: Kompleksitas dan pilihan konstruksi
Dengan suffix array yang sudah disediakan, setiap perbandingan memeriksa paling banyak m karakter dan pencarian biner melakukan perbandingan O(log n), sehingga kueri beroperasi dalam O(m log n + z). Stanford secara eksplisit memisahkan biaya pelaporan O(z). Konstruksi pembelajaran dapat mengurutkan potongan (slice) sufiks, tetapi ini menyalin data dan lambat; produksi harus menggunakan penggandaan prefiks (prefix doubling), SA-IS, atau pustaka yang teruji. Materi MIT dan Stanford memposisikan suffix array sebagai indeks teks tetap yang menghemat ruang pointer yang besar dibandingkan dengan suffix tree.
Implementasi Python yang dapat dieksekusi
def build_suffix_array(text):
# Teaching build for verification, not a production complexity claim.
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])Kode ini memisahkan konstruksi dan kueri. Pengurutan akhir mengembalikan indeks awal sesuai urutan teks; hilangkan jika urutan suffix array adalah kontrak API yang diminta. Teks kosong, pola kosong, tidak ada kecocokan, dan kecocokan berulang adalah kasus uji langsung.
Contoh jawaban berkualitas tinggi
"Pertama-tama saya memastikan bahwa teks bersifat tetap dan menerima banyak pola, lalu menyimpan setiap awal sufiks dalam urutan leksikografis. Karena sebuah pola merupakan prefiks umum dari sufiks yang cocok, semua jawaban menempati rentang yang berurutan. Dua batas bawah menemukan rentang tersebut; perbandingan hanya memeriksa sepanjang pola dan menganggap sufiks yang lebih pendek sebagai lebih kecil. Dengan array yang diberikan, kueri adalah O(m log n + z), di mana z adalah keluaran. Pembuatan untuk tujuan edukasi dapat menggunakan pengurutan, tetapi indeks besar membutuhkan penggandaan prefiks, SA-IS, atau implementasi yang teruji, dengan kebijakan normalisasi karakter yang ditentukan."
Kesalahan umum
- Mengembalikan kecocokan pertama → kemunculan yang berdekatan terlewat → gunakan pencarian biner untuk kedua batas.
- Membandingkan string sufiks lengkap dengan pola → batas sufiks pendek menjadi salah → tentukan perbandingan prefiks dan aturan sufiks yang lebih pendek.
- Membebankan biaya konstruksi ke setiap kueri → skenario teks tetap tidak dijelaskan → laporkan biaya pembuatan satu kali dan biaya per kueri secara terpisah.
- Menyebut interval suffix array sebagai urutan teks → pemanggil melihat urutan yang tidak stabil → urutkan indeks awal jika diperlukan atau dokumentasikan urutannya.
- Melupakan posisi n+1 untuk pola kosong → kontrak yang dinyatakan dilanggar → tangani pola kosong terlebih dahulu.
Pertanyaan lanjutan dan respons yang kuat
Bagaimana cara mengurangi perbandingan karakter yang berulang untuk pola yang panjang?
Tambahkan informasi LCP (Longest Common Prefix) untuk sufiks yang bertetangga dan gunakan kembali prefiks umum yang diketahui selama pencarian biner. Ini dapat mendekati O(m + log n), tetapi membutuhkan status LCP tambahan dan invarian yang lebih kuat; tanpa itu, nyatakan O(m log n) apa adanya.
Apakah Anda akan menggunakan suffix array jika teks sering berubah?
Tidak sebagai satu indeks statis. Pembangunan ulang secara berkala (batch rebuilds), indeks tingkat segmen dengan penggabungan di kemudian hari, atau matcher online mungkin lebih cocok. Pilih berdasarkan tingkat pembaruan, volume kueri, dan penundaan pembangunan ulang yang dapat diterima.
Bagaimana cara menguji bahwa batas pencarian biner sudah benar?
Bandingkan dengan pemindaian brute-force pada teks dan pola kecil acak. Sertakan pola kosong, karakter berulang, pola yang lebih panjang dari teks, tanpa kecocokan, dan setiap posisi cocok. Pastikan (assert) bahwa posisi tetangga di luar rentang gagal memenuhi predikat prefiks.
Mengapa tidak menggunakan KMP secara langsung?
Untuk satu pola dan satu kali pemindaian teks, KMP lebih sederhana pada O(n+m). Suffix array bermanfaat untuk banyak pola pada teks tetap dan untuk operasi offline yang melibatkan substring berulang, LCP, atau BWT.