Temuduga Pengekodan: Bagaimanakah anda mengekalkan subrentetan palindromik berbeza secara dalam talian dengan eertree?

Masalah dan Konteks

Diberikan satu strim s[0..n), satu aksara ditambah pada satu-satu masa. Selepas setiap penambahan, kekalkan bilangan subrentetan palindromik berbeza, kiraan kemunculan bagi setiap palindrom, dan akhiran palindromik terpanjang bagi awalan semasa. Penyelesaian mestilah secara dalam talian dan bukannya menyenaraikan semula semua subrentetan selepas setiap penambahan.

Sebuah eertree (pokok palindromik) menyimpan satu nod bagi setiap palindrom berbeza. Tepi menambah aksara yang sama pada kedua-dua hujung, manakala pautan akhiran (suffix link) menunjuk kepada akhiran palindromik wajar yang terpanjang. Jawapan yang mantap menerangkan dua punca sentinel, cara akhiran yang boleh dipanjangkan ditemui, dan sebab paling banyak satu nod dicipta bagi setiap kedudukan.

Perkara yang Dinilai oleh Penemu Duga

Membezakan punca panjang -1 dan panjang 0 dengan betul.
Memahami last, akhiran palindromik terpanjang, dan pautan akhiran.
Mencari nod yang boleh dipanjangkan dan mencipta peralihan semasa penambahan.
Mengetahui batas nod, masa, dan ruang O(n) di bawah model penambahan.
Mengendalikan aksara berulang, rentetan kosong, perwakilan abjad, dan perambatan kiraan.
Memperluas struktur kepada pembahagian palindrom atau varian tetingkap gelongsor.

Penjelasan untuk Ditanya Terlebih Dahulu

Adakah input merupakan rentetan sekali gus atau strim yang hanya menambah di sebelah kanan? Adakah bahagian kiri perlu dipadamkan?
Patutkah kemunculan dikira mengikut kedudukan penamat atau sebagai jumlah kekerapan akhir?
Adakah abjad mengandungi huruf kecil, Unicode, atau token integer sebarangan?
Patutkah output mengandungi teks palindrom, id nod, atau hanya panjang dan kiraan?
Adakah potongan minimum dalam talian diperlukan, atau memadai dengan mengekalkan set palindrom berbeza?

Rangka Kerja Jawapan 30 Saat

Saya menggunakan dua punca: panjang -1 dan panjang 0. Setiap nod biasa menyimpan panjang palindromnya, pautan akhiran ke akhiran palindromik wajar terpanjang, dan peralihan aksara. last ialah akhiran palindromik terpanjang bagi awalan semasa. Apabila aksara c tiba, saya mengikut pautan akhiran sehingga kedua-dua belah boleh dibalut oleh c; saya menggunakan semula peralihan sedia ada atau mencipta peralihan baharu, kemudian mengira pautan akhiran nod baharu daripada rantai pautan. Paling banyak satu nod berbeza boleh ditambah bagi setiap kedudukan, jadi pembinaan adalah O(n), dan merambat kiraan kemunculan dalam susunan pautan akhiran songsang menghasilkan kekerapan akhir.

Perbincangan Mendalam Langkah demi Langkah

1. Dua Punca dan Medan Nod

Punca ganjil mempunyai panjang -1, bertindak sebagai sentinel yang boleh dipanjangkan oleh mana-mana aksara. Punca genap mempunyai panjang 0 dan mewakili palindrom kosong. Nod biasa menyimpan len, link, next, occ, dan secara pilihan kedudukan penamat. last bermula pada punca genap.

2. Cari Akhiran yang Boleh Dipanjangkan

Selepas menambah c pada kedudukan pos, mulakan daripada last dan uji sama ada aksara sebelum palindrom nod tersebut sama dengan c. Jika tidak, tetapkan v = link[v] dan teruskan. Padanan pertama ialah akhiran palindromik terpanjang yang boleh dipanjangkan.

text

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

Pelaksanaan lazimnya menambah sentinel di luar abjad di bahagian hadapan supaya semakan punca ganjil tidak sekali-kali membaca indeks negatif.

3. Tambah Peralihan dan Nod

Jika next[v][c] sudah wujud, ia menjadi last baharu dan occ miliknya bertambah. Jika tidak, cipta nod dengan panjang len[v] + 2 dan tetapkan peralihan. Nod dengan panjang satu memaut terus ke punca genap. Bagi nod yang lebih panjang, ikuti link[v] sehingga peralihan sepadan pada c ditemui.

4. Mengapa Hanya Satu Nod Ditambah

Setiap palindrom yang baru dicipta oleh satu penambahan mesti berakhir pada aksara baharu. Hanya palindrom terpanjang yang sedemikian adalah baharu; akhiran palindromiknya yang lebih pendek telah sedia ada pada rantai pautan akhiran. Oleh itu, setiap kedudukan mencipta paling banyak satu nod berbeza, mengekalkan jumlah nod paling banyak n + 2.

5. Rambat Kiraan Kemunculan

Semasa laluan dalam talian, tingkatkan occ untuk akhiran palindromik terpanjang yang berakhir pada setiap kedudukan. Selepas input tamat, proses nod daripada yang lebih panjang kepada yang lebih pendek dan tambahkan occ[v] ke dalam occ[link[v]]. Ini memindahkan setiap kemunculan kepada semua akhiran palindromiknya. Untuk mendapatkan kiraan berbeza sahaja, kembalikan bilangan nod biasa.

6. Lanjutkan kepada Pembahagian Palindrom

Untuk potongan palindrom minimum, senaraikan palindrom yang berakhir pada setiap kedudukan dengan menelusuri rantai pautan akhiran last dan kemas kini dp[pos] = min(dp[pos - len[v]] + 1). Penelusuran rantai secara naif boleh menjadi O(n^2). Pautan siri boleh mengelompokkan larian perbezaan panjang yang sama, tetapi pengoptimuman ini harus dipilih hanya selepas mengesahkan kekangan.

7. Sempadan, Abjad, dan Kekompleksan

Input kosong hanya mempunyai dua punca. Aksara berulang menggunakan semula peralihan dan tidak boleh mencipta nod pendua. Abjad kecil boleh menggunakan tatasusunan tetap dengan storan peralihan O(n * alphabet); abjad besar memerlukan peta cincangan atau peta bertertib, memberikan tingkah laku dijangka O(n) atau O(n log σ). Di bawah model penambahan kanan sahaja, pembinaan adalah O(n) dengan peralihan cincangan masa malar dijangka, dan ruang adalah O(n) ditambah storan peralihan.

Jawapan Model Berkualiti Tinggi

Saya akan mengesahkan terlebih dahulu penambahan kanan sahaja, jenis abjad, dan maksud kiraan kemunculan. Struktur ini mempunyai punca panjang -1 dan 0; nod biasa mewakili palindrom berbeza, dan last ialah akhiran palindromik terpanjang bagi awalan semasa. Bagi setiap c yang ditambah, saya mengikuti pautan akhiran ke nod terpanjang yang boleh membalut c. Jika peralihannya tiada, saya mencipta nod dengan panjang len + 2; nod dengan panjang satu memaut ke punca genap, manakala nod yang lebih panjang mencari pautannya melalui rantai pautan akhiran induk. Paling banyak satu nod dicipta bagi setiap kedudukan, jadi pembinaan adalah linear. Merekodkan setiap last dan merambat kiraan daripada nod yang lebih panjang ke pautannya menghasilkan jumlah kekerapan akhir. Pemadaman dari kiri, penyisipan sebarangan, atau abjad yang besar memerlukan penilaian semula struktur dan kekompleksan.

Kesilapan Biasa

Menggunakan satu punca kosong sahaja → sempadan ganjil dan genap menjadi janggal → kekalkan kedua-dua punca -1 dan 0.
Bermula semula dari punca bagi setiap penambahan → kehilangan sifat linear dalam talian → ikuti pautan akhiran dari last.
Menganggap last sebagai palindrom terpanjang di mana-mana → ia hanyalah akhiran palindromik terpanjang.
Memautkan nod baharu ke induknya → pautan mesti menyasarkan akhiran palindromik wajar terpanjang.
Meningkatkan setiap palindrom pada setiap penambahan → kiraan berganda → rekod nod penamat dan rambat dalam susunan pautan songsang.
Menggunakan tatasusunan tetap yang kecil untuk Unicode sebarangan → perlanggaran atau limpahan → tentukan pengekodan dan pemetaan secara eksplisit.

Soalan Susulan dan Maklum Balas

Bilakah anda akan memilih Manacher sebagai ganti?

Manacher amat sesuai untuk rentetan statik apabila satu-satunya keperluan adalah jejari terpanjang pada setiap pusat. Eertree mewakili setiap palindrom berbeza dan menyokong penambahan dalam talian, kiraan peringkat nod, dan pertanyaan pautan akhiran secara semula jadi.

Bagaimanakah anda mengembalikan teks palindrom terpanjang semasa?

Simpan kedudukan penamat pada setiap nod. Pasangan kedudukan itu dan len mengenal pasti potongan dalam input yang dikekalkan. Strim yang membuang input memerlukan penimbal gelang (ring buffer) atau storan luaran.

Mengapa merambat kiraan dalam susunan songsang?

Setiap kemunculan palindrom yang lebih panjang juga merupakan kemunculan bagi setiap akhiran palindromik pada laluan pautannya. Memproses nod yang lebih panjang terlebih dahulu memastikan setiap sumbangan anak selesai sebelum ia ditambah kepada induknya.

Bolehkah struktur ini memadam dari sebelah kiri?

Eertree biasa hanya menyokong penambahan di sebelah kanan. Tetingkap gelongsor memerlukan varian dua hujung atau pembinaan semula/penyekatan; pilihan bergantung pada saiz tetingkap dan kadar pemadaman.

Apakah yang berubah dengan peralihan peta cincangan?

Peta cincangan memberikan carian peralihan dijangka O(1) dan pembinaan dijangka O(n). Tingkah laku kes terburuk bergantung pada pelaksanaan cincangan. Peta bertertib memberikan batas kepastian (deterministik) dengan faktor O(log σ).