Apakah ada algoritma untuk memeriksa apakah sebuah string merupakan catenation dari palindrom?

Apakah ada algoritma linear-waktu untuk memeriksa bahwa urutan karakter adalah gabungan palindrom? Satu-satunya hal yang terlintas di benak saya adalah solusi naif:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Catatan: jawabannya sepele ya jika panjang 1-string didefinisikan sebagai palindrom. Mari kita asumsikan bahwa ini bukan masalahnya.

algorithms efficiency strings saadtaame
sumber

Jika Anda mengizinkan palindrom sepele dengan panjang 1 (mis. String "a" adalah palindrom) maka semua string adalah gabungan palindrom.

Matt Lewis

Apakah ini berguna, atau latihan?

Jan Hudec

@ MatLewis Anda dapat mencoba meminimalkan jumlah palindrom. Jan, kenapa? Kedengarannya seperti latihan yang bagus dalam pemrograman dinamis.

Pål GD

@Haile No. Disjoint palindromes saja.

saadtaame

Norvig melakukan pekerjaan yang luas di Palindrom. Anda mungkin tertarik pada halaman ini: norvig.com/palindrome.html

robowolverine

Jawaban:

Dengan asumsi Anda ingin memisahkan palindrom, ini dikenal sebagai masalah PALSTAR, dan ada algoritma waktu linier oleh Zvi Galil dan Joel Seiferas. Algoritma Pengenalan On-Line Linear-Waktu untuk `` Palstar ' .

Anda dapat menemukan penjelasan algoritma dalam buku di sini: Algoritma Teks (lihat halaman yang ditautkan dan halaman sebelumnya).

Jika Anda baik-baik saja dengan algoritma waktu kuadrat, pemrograman dinamis langsung tampaknya berfungsi.

Diberi string $s[1,\dots n]$ , kami mempertahankan array yang memberi tahu kami apakah $s[1,\dots j]$ dapat didekomposisi menjadi palindrom.

Kami juga memelihara tabel 2D yang memberi tahu kami apakah $s[i, \dots j]$ adalah palindrome atau bukan. Ini dapat kita bangun $O(n^2)$ waktu dengan memilih pusat dan memindahkan dua petunjuk ke luar, memeriksa palindrom dengan pusat itu. Lakukan ini untuk setiap pusat yang mungkin: $\Theta(n)$ pusat, masing-masing mengambil $O(n)$ waktu.

Sekarang, kamu bisa memeriksanya $s[1, \dots j+1]$ apakah dapat didekomposisi menjadi palindrom, dengan memeriksa masing-masing $1 \le i \le j-1$ apakah $s[1,\dots i]$ dapat diuraikan, dan jika $s[i+1,\dots, j+1]$ adalah palindrome (menggunakan tabel 2D di atas). Ini menghasilkan a $\Theta(n^2)$ waktu dan $\Theta(n^2)$ algoritma ruang.

Penggunaan ruang dapat diturunkan ke $O(n)$ , jika Anda menggunakan algoritma on-line Manacher untuk menghitung apakah $s[i+1,\dots j+1]$ adalah palindrome (as $i$ pergi dari $j-1$ untuk $1$ ), pada dasarnya menyingkirkan tabel 2D.

Aryabhata
sumber

Ini mirip dengan algoritma saya, saya hanya tidak menjelaskan bagian preprocessing untuk membiarkannya sebagai latihan untuk OP, tapi saya tidak tahu mengapa tidak ada yang peduli dengan algoritma saya :)

@ SaeedAmiri: Sudahkah Anda membaca bagian pertama dari jawaban saya yang menyebutkan waktu linear? Bagaimana itu serupa? btw, OP mengubah pertanyaan untuk meminta algoritma waktu linier, yang membuat jawaban Anda, dan bagian terakhir dari jawaban saya tidak relevan. Saya tidak menghapus bagian itu dari jawaban saya, karena saya ingin menyebutkan algoritma Manacher yang membuat algoritma pemrograman dinamis hanya menggunakan ruang O (n) (dan menghilangkan langkah preprocessing), dan mungkin masih relevan dengan orang lain yang kebetulan menemukan pertanyaan ini

Aryabhata

Jangan ambil seri, itu hanya bercanda, saya suka jawaban Anda secara umum, saya pikir ada masalah dengan tulisan bahasa Inggris saya, karena OP tidak mengerti solusi saya, dan itu keluar dari mood saya untuk menggambar dengan gambar . Tapi poin bagus OP mengubah pertanyaannya baru-baru ini, dan mungkin ada solusi yang mirip dengan algoritma Manacher (tapi sebenarnya tidak mudah).

@ SaeedAmiri: Begitu ya, jangan khawatir :-)

Aryabhata

Jika tumpang tindih diperbolehkan, itu bisa dilakukan dalam waktu linier (dalam ukuran string input).

Beberapa definisi

Mari kita mendefinisikan konsep palindrome maksimal :

Sebuah palindrom maksimal radius k dari string S adalah substring S' seperti yang

mulai dari tengah, S 'membaca karakter k yang sama di kedua arah
tetapi tidak untuk k + 1 karakter
k> 1 (jadi satu karakter bukan palindrome)

misalnya, jika S = banana, maka S' = ananaadalah palindrome maksimal jari-jari 2.

Sebuah palindrom maksimal adalah palindrom maksimal radius k untuk beberapa k.

Sebagai contoh, jika S = banana, "ana", "anana", semua palindrom maksimal nya.

Menggunakan palindrom maksimal

Sekarang, jika kita dapat menemukan semua palindrom maksimal string , akan mudah untuk memeriksa apakah seluruh string adalah gabungan palindrom.

Ambil S = abbaccazayaz. Palindrom maksimalnya adalah:

abba, berpusat di antara posisi 2 dan 3, jari-jari = 2
ACCA, berpusat di antara posisi 5 dan 6, jari-jari = 2
zayaz, berpusat di posisi 10, jari-jari = 2

jadi "abba" membentang [1..4], "acca" membentang [4..7], "zayaz" membentang [8..12]. Karena rangkaian ketiga palindrom ini (tumpang tindih diizinkan?) Mencakup seluruh string, maka "abbaccazayaz" adalah gabungan palindrom.

Menghitung palindrom maksimal dalam waktu linier

Sekarang, ternyata kita dapat menemukan semua palindrom maksimal dari string S dalam waktu linier !*

Idenya adalah untuk menggunakan pohon sufiks untuk S yang dilengkapi dengan permintaan leluhur umum terendah yang konstan dan waktu .

Jadi kita dapat memeriksa apakah string S dengan panjang m adalah gabungan palindrom dalam waktu O (n).

* Gusfield, Dan (1997), "9.2 Menemukan semua palindrom maksimal dalam waktu linier", Algoritma pada Strings, Trees, and Sequences

Salam
sumber

Dengan asumsi palindrom yang tumpang tindih diperbolehkan dan kami sedang mencari urutan palindrom terkecil, saya tidak melihat mengapa ini harus mengembalikan yang terkecil (meskipun saya tidak memiliki contoh tandingan). Jika kami memeriksa apakah mungkin dengan palindrom radius setidaknya

k

$k$ , maka memang bermanfaat. Juga, nanabukan palindrome, saya kira Anda maksudkan ananasebagai gantinya.

Khaur

Mengedit hal "anana", terima kasih. Juga, OP tidak meminta urutan palindrom minimal: mengingat bahwa char tunggal bukan palindrom, kita hanya harus memutuskan apakah string input adalah gabungan palindrom atau tidak.

Haile

Karakter tunggal adalah palindrom (meskipun tidak menarik). Jika Anda menganggap mereka tidak, maka Anda memecahkan masalah kedua yang saya sebutkan

k = 1

$k=1$ . Pada catatan kompleksitas, setelah Anda menghitung semua palindrom maksimal, Anda masih harus memeriksa mereka span seluruh urutan, yang IIRC membutuhkan waktu loglinear dalam jumlah palindrom (yang bisa hampir setinggi panjang urutan dalam kasus patologis) . Pokoknya saya pikir Anda harus lebih menekankan bahwa Anda menganggap tumpang tindih diperbolehkan, karena itu bukan asumsi yang jelas.

Khaur

@ Kamur Hanya perlu waktu loglinear jika intervalnya tidak diurutkan. Dalam hal ini mereka mungkin.

Yuval Filmus

Dalam komentar pada pertanyaan, OP secara eksplisit menambahkan bahwa palindrom yang tumpang tindih tidak diperbolehkan. Jadi solusi ini dalam bentuk yang sekarang bukan yang dicari OP. Saya pikir solusi ini dapat dimodifikasi untuk menyelesaikan kasus yang tidak tumpang tindih juga, dengan beberapa pemikiran dan kompleksitas kuadrat yang paling tinggi. Tapi saya belum memikirkannya.

Paresh

Misalkan Palindrome [] [] adalah larik dan Palindrom (i, j) adalah fungsi yang memeriksa, apakah substring dari i ke j adalah palindrome dan mengembalikan 1 jika palindrom atau mengembalikan infinity jika bukan palindrom, dan Anda mencari angka terkecil partisi, buat dari bawah ke atas:

P a l i n d r o m e [i] [i] = 1.

$Palindrome[i][i] = 1.$

\forall 0 \leq i < j < n : P a l i n d r o m e [i] [j] = min {P a l i n d r o m e (i, j), min_{i \leq k < j} {P a l i n d r o m e [i, k] + P a l i n d r o m e [i + 1, k]}}

$\forall 0\le i < j < n : Palindrome[i][j] = \min\{Palindrome(i,j), \min_{i\le k<j} \{Palindrome[i,k] + Palindrome[i+1,k]\}\}$

Anda harus mengisi $O(n^2)$ sel dan masing-masing sel membutuhkan paling banyak $O(n)$ jadi algoritma $O(n^3)$ , dengan sedikit modifikasi (preprocessing) Anda dapat memperbaikinya $O(n^2)$ , Juga menemukan partisi ini tidak sulit.

sumber

Bisakah Anda memberi ilustrasi dengan sebuah contoh? Katakan:abbaaccaabba.

saadtaame

@saadtaame, OK, di sini tidak mungkin membuat tabel (di cs.stackexchange), atau saya tidak bisa menemukan cara untuk melakukan ini, saya akan melakukan ini di suatu tempat dan saya akan meletakkan gambar di sini nanti. tetapi untuk sekarang Anda mencoba memahaminya sendiri, mulai dari substring dengan panjang 1, lalu periksa palindrom dengan panjang 2, .... dan seterusnya.