Wawancara Coding: Bagaimana Anda mempertahankan substring palindromik unik secara online dengan eertree?

Masalah dan Konteks

Diberikan sebuah stream s[0..n), satu karakter ditambahkan pada satu waktu. Setelah setiap append, pertahankan jumlah substring palindromik unik, jumlah kemunculan untuk setiap palindrom, dan sufiks palindromik terpanjang dari prefiks saat ini. Solusi harus bersifat online daripada menghitung ulang semua substring setelah setiap penambahan.

Sebuah eertree (pohon palindromik) menyimpan satu simpul per palindrom unik. Tepi (edges) menambahkan karakter yang sama di kedua ujungnya, sementara tautan sufiks (suffix link) menunjuk ke sufiks palindromik sejati (proper palindromic suffix) terpanjang. Jawaban yang kuat menjelaskan dua root sentinel, bagaimana sufiks yang dapat diperluas ditemukan, dan mengapa paling banyak satu simpul dibuat per posisi.

Apa yang Dievaluasi oleh Pewawancara

Membedakan secara benar root dengan panjang -1 dan panjang 0.
Memahami last, sufiks palindromik terpanjang, dan tautan sufiks.
Menemukan simpul yang dapat diperluas dan membuat transisi selama proses append.
Mengetahui batas simpul, waktu, dan ruang O(n) di bawah model append.
Menangani karakter berulang, string kosong, representasi alfabet, dan propagasi hitungan.
Memperluas struktur ke partisi palindrom atau varian sliding-window.

Klarifikasi yang Perlu Ditanyakan Terlebih Dahulu

Apakah input berupa string satu kali atau stream yang hanya menambahkan di sisi kanan? Apakah sisi kiri harus dihapus?
Apakah kemunculan harus dihitung berdasarkan posisi akhir atau sebagai frekuensi total akhir?
Apakah alfabet berupa huruf kecil, Unicode, atau token bilangan bulat arbitrer?
Apakah output harus berisi teks palindrom, ID simpul, atau hanya panjang dan hitungan?
Apakah pemotongan minimum (minimum cuts) online diperlukan, atau cukup mempertahankan himpunan palindrom unik?

Kerangka Jawaban 30 Detik

Saya menggunakan dua root: panjang -1 dan panjang 0. Setiap simpul biasa menyimpan panjang palindromnya, tautan sufiks ke sufiks palindromik sejati terpanjang, dan transisi karakter. last adalah sufiks palindromik terpanjang dari prefiks saat ini. Ketika karakter c tiba, saya mengikuti tautan sufiks hingga kedua sisi dapat dibungkus oleh c; saya menggunakan kembali transisi yang ada atau membuatnya baru, kemudian menghitung tautan sufiks simpul baru dari rantai tautan. Paling banyak satu simpul unik dapat ditambahkan per posisi, sehingga konstruksinya adalah O(n), dan mempropagasikan jumlah kemunculan dalam urutan tautan sufiks terbalik menghasilkan frekuensi akhir.

Pembahasan Mendalam Langkah demi Langkah

1. Dua Root dan Field Simpul

Root ganjil memiliki panjang -1, bertindak sebagai sentinel yang dapat diperluas oleh karakter apa pun. Root genap memiliki panjang 0 dan merepresentasikan palindrom kosong. Simpul biasa menyimpan len, link, next, occ, dan secara opsional posisi akhir. last dimulai pada root genap.

2. Menemukan Sufiks yang Dapat Diperluas

Setelah menambahkan c pada posisi pos, mulai dari last dan uji apakah karakter tepat sebelum palindrom simpul tersebut sama dengan c. Jika tidak, atur v = link[v] dan lanjutkan. Kecocokan pertama adalah sufiks palindromik terpanjang yang dapat diperluas.

text

while s[pos - 1 - len[v]] != c:
    v = link[v]

Implementasi umumnya menambahkan sentinel di luar alfabet di awal sehingga pemeriksaan root ganjil tidak pernah membaca indeks negatif.

3. Menambahkan Transisi dan Simpul

Jika next[v][c] sudah ada, simpul tersebut menjadi last baru dan occ miliknya bertambah. Jika tidak, buat simpul dengan panjang len[v] + 2 dan tetapkan transisinya. Simpul dengan panjang satu terhubung langsung ke root genap. Untuk simpul yang lebih panjang, ikuti link[v] hingga transisi yang sesuai pada c ditemukan.

4. Mengapa Hanya Satu Simpul yang Ditambahkan

Setiap palindrom yang baru dibuat oleh satu operasi append harus berakhir pada karakter baru tersebut. Hanya palindrom terpanjang semacam itu yang baru; sufiks palindromiknya yang lebih pendek sudah ada pada rantai tautan sufiks. Oleh karena itu, setiap posisi membuat paling banyak satu simpul unik, menjaga total simpul paling banyak n + 2.

5. Mempropagasikan Jumlah Kemunculan

Selama lintasan online, tingkatkan occ untuk sufiks palindromik terpanjang yang berakhir di setiap posisi. Setelah input berakhir, proses simpul dari yang lebih panjang ke yang lebih pendek dan tambahkan occ[v] ke dalam occ[link[v]]. Ini mentransfer setiap kemunculan ke semua sufiks palindromiknya. Jika hanya memerlukan jumlah unik, kembalikan banyaknya simpul biasa.

6. Memperluas ke Partisi Palindrom

Untuk pemotongan palindrom minimum, hitung palindrom yang berakhir di setiap posisi dengan menelusuri rantai tautan sufiks last dan perbarui dp[pos] = min(dp[pos - len[v]] + 1). Penelusuran rantai secara naif dapat menjadi O(n^2). Tautan deret (series links) dapat mengelompokkan rentetan perbedaan panjang yang sama, tetapi optimasi ini harus dipilih hanya setelah mengonfirmasi batasan-batasan yang ada.

7. Batas, Alfabet, dan Kompleksitas

Input kosong hanya memiliki dua root. Karakter berulang menggunakan kembali transisi dan tidak boleh membuat simpul duplikat. Alfabet kecil dapat menggunakan array tetap dengan penyimpanan transisi O(n * alphabet); alfabet besar membutuhkan hash map atau ordered map, menghasilkan perilaku yang diharapkan O(n) atau O(n log σ). Di bawah append khusus kanan, konstruksi adalah O(n) dengan transisi hash waktu konstan yang diharapkan, dan ruang adalah O(n) ditambah penyimpanan transisi.

Jawaban Model Berkualitas Tinggi

Pertama-tama saya akan mengonfirmasi operasi append khusus kanan, alfabet, dan apa arti dari hitungan kemunculan. Struktur ini memiliki root dengan panjang -1 dan 0; simpul biasa merepresentasikan palindrom unik, dan last adalah sufiks palindromik terpanjang dari prefiks saat ini. Untuk setiap c yang ditambahkan, saya mengikuti tautan sufiks ke simpul terpanjang yang dapat dibungkus oleh c. Jika transisinya tidak ada, saya membuat simpul dengan panjang len + 2; simpul dengan panjang satu menautkan ke root genap, sedangkan simpul yang lebih panjang menemukan tautannya melalui rantai tautan sufiks induknya. Paling banyak satu simpul dibuat per posisi, sehingga konstruksinya linier. Mencatat setiap last dan mempropagasikan hitungan dari simpul yang lebih panjang ke tautannya menghasilkan frekuensi total. Penghapusan dari kiri, penyisipan arbitrer, atau alfabet besar memerlukan peninjauan kembali struktur dan kompleksitasnya.

Kesalahan Umum

Menggunakan satu root kosong → batas ganjil dan genap menjadi rumit → pertahankan kedua root -1 dan 0.
Memulai ulang dari root untuk setiap append → kehilangan properti linier online → ikuti tautan sufiks dari last.
Memperlakukan last sebagai palindrom terpanjang di mana saja → itu hanya sufiks palindromik terpanjang.
Menautkan simpul baru ke induknya → tautan harus menargetkan sufiks palindromik sejati terpanjang.
Menambahkan setiap palindrom pada setiap append → terjadi penghitungan ganda → catat simpul akhir dan variasikan propagasi dalam urutan tautan terbalik.
Menerapkan array tetap kecil untuk Unicode arbitrer → tabrakan atau luapan → tentukan pengkodean dan pemetaan secara eksplisit.

Pertanyaan Lanjutan dan Tanggapan

Kapan Anda akan memilih Manacher sebagai gantinya?

Manacher cocok untuk string statis ketika satu-satunya kebutuhan adalah jari-jari terpanjang di setiap titik pusat. Eertree merepresentasikan setiap palindrom unik dan secara alami mendukung penambahan online, hitungan tingkat simpul, dan kueri tautan sufiks.

Bagaimana Anda mengembalikan teks palindrom terpanjang saat ini?

Simpan posisi akhir pada setiap simpul. Pasangan dari posisi tersebut dan len mengidentifikasi potongan (slice) dalam input yang dipertahankan. Stream yang membuang input memerlukan buffer sirkular (ring buffer) atau penyimpanan eksternal.

Mengapa mempropagasikan hitungan dalam urutan terbalik?

Setiap kemunculan palindrom yang lebih panjang juga merupakan kemunculan dari setiap sufiks palindromik pada jalur tautannya. Memproses simpul yang lebih panjang terlebih dahulu memastikan kontribusi setiap anak lengkap sebelum ditambahkan ke induknya.

Bisakah struktur ini menghapus dari kiri?

Eertree biasa hanya mendukung penambahan di sisi kanan. Sliding window membutuhkan varian berujung ganda (double-ended) atau pembangunan ulang/pemblokiran; pilihannya tergantung pada ukuran jendela dan tingkat penghapusan.

Apa yang berubah dengan transisi hash-map?

Hash map memberikan pencarian transisi dengan waktu yang diharapkan O(1) dan konstruksi dengan waktu yang diharapkan O(n). Perilaku kasus terburuk tergantung pada implementasi hash. Ordered map menyediakan batas deterministik dengan faktor O(log σ).