Menemukan pengulangan terpanjang

Diberikan string , saya ingin mencari pengulangan terpanjang (setidaknya dua kali). Yaitu, saya ingin mencari string yang merupakan urutan (tidak harus bersebelahan) dari sehingga . Artinya, adalah string yang bagiannya muncul dua kali berturut-turut. Perhatikan bahwa adalah lanjutan dari , tetapi tidak harus berupa substring. $s$ $w$ $s$ $w=w' \cdot w'$ $w$ $w$ $s$

Contoh:

Untuk 'ababccabdc' akan menjadi 'abcabc', karena 'abc' = 'abc' dan 'abc' muncul (setidaknya) dua kali dalam 'ababccabdc'.

Untuk 'addbacddabcd' satu opsi adalah 'dddd' karena 'dd' muncul dua kali (saya tidak dapat menggunakan huruf yang sama beberapa kali, tapi di sini saya punya 4 'd begitu ok), tetapi dengan lebngth 4. Saya dapat menemukan yang lebih baik dengan panjang 8: 'abcdabcd', karena 'abcd' adalah substring dari 'addbacddabcd' yang muncul dua kali.

Saya tertarik untuk menemukan urutan berulang terlama. Ini juga disebut "menemukan kuadrat terpanjang / terbesar", tetapi saya telah membaca banyak artikel di mana kuadrat didefinisikan untuk substring dan bukan untuk urutan berikutnya.

Saya dapat dengan mudah menggunakan algoritma brute force yang akan mengambil dengan mengulangi semua opsi untuk breakpoint dalam string, dan kemudian saya akan memiliki dua string di mana saya akan mencari urutan umum terbesar / terpanjang, tetapi setiap cek akan mengambil menggunakan teknik pemrograman dinamis, sehingga seluruh waktu akan menjadi . Saya menemukan algoritma yang lebih efisien untuk urutan umum terpanjang yang mengambil , sehingga waktu berjalan akan menjadi . $O(n^3)$ $O(n^2)$ $O(n^3)$ $O(\frac{n^2}{\log n})$ $O(\frac{n^3}{\log n})$

Saya mencari algoritma yang lebih efisien untuk masalah pengulangan terpanjang. Mungkin ide saya tentang iterasi pada semua breakpoint menghabiskan banyak waktu, dan dapat dikurangi menjadi iterasi yang lebih sedikit. Atau mungkin suatu algoritma dengan sikap yang berbeda dapat menyelesaikan masalah ini.

Saya telah mencari di banyak jurnal dan pertanyaan sebelumnya, dan sebagian besar hasil yang saya temukan adalah tentang substring dan bukan tentang berikutnya.

Saya juga membaca bahwa ini dapat dilakukan dengan menggunakan pohon suffix, tetapi ini juga relevan dengan substring dan saya tidak yakin apakah ide seperti itu dapat diperpanjang untuk selanjutnya.

Saya mencari solusi yang berjalan dalam waktu . Jika ada satu dalam waktu yang akan lebih baik (saya tidak yakin apakah ada). $O(n^2)$ $O(n \cdot \log n)$

algorithms optimization dynamic-programming strings subsequences Dan D-man
sumber

Cari pohon sufiks atau susunan sufiks.

Nama samaran

Sangat tidak mungkin bahwa algoritma -waktu ada untuk masalah ini, karena jika itu terjadi, Anda dapat menggunakannya untuk mengalahkan algoritma yang paling dikenal untuk menemukan LCS dari dua string panjang- dan sebagai berikut: Bentuk string , di mana adalah salinan karakter yang tidak muncul di atau , dan kemudian jalankan algoritma -waktu Anda di atasnya. Kedua "belahan" dari urutan berulang terlama akan selalu dimulai dengan , sehingga setengahnya berasal dari masing-masing dari dan

o (n^{2})

$o(n^2)$

n

$n$

u

$u$

v

$v$

x u x v

$xuxv$

x

$x$

n + 1

$n+1$ $

u

$u$

v

$v$

o (n^{2})

$o(n^2)$

x

$x$

u

$u$

v

$v$ , memecahkan masalah LCS.

j_random_hacker

@j_random_hacker LCS dapat diselesaikan di menggunakan Suffix Tree atau di menggunakan hash bergulir.

O (n + m)

$\mathcal O(n+m)$

O (n \log n)

$\mathcal O(n\log n)$

Evil

@ Evil: Saya belum melihat caranya, bisakah Anda memberikan sedikit lebih detail? (Apakah Anda yakin tidak memikirkan string Sub Long Biasa , yang dapat diselesaikan dalam kompleksitas waktu itu?)

j_random_hacker

@ j_random_hacker Saya pikir Anda membandingkan tujuan dengan LCS (berturut-turut), tetapi di sini, seperti yang Anda sebutkan, ya, saya bahkan belum melihat solusi yang bekerja di n ^ 2 untuk Pemanjangan Umum Terpanjang (saya telah menemukan satu kode pemrograman dinamis, disebarkan ke banyak halaman, yang cacat, mirip dengan jawaban downvoted). Jadi saya salah mengerti komentar Anda, maaf.

o (n^{2})

$o(n^2)$

Evil

Berikut ini adalah solusi pemrograman dinamis.

Misalkan string input adalah . Buat tabel yang baris dan kolomnya diindeks oleh (dengan adalah panjang dari string), diisi oleh aturan Jawabannya adalah . $x_1\ldots x_n$ $T$ $0,\ldots,n$ $n$

T [i, j] = {\begin{cases} 0 & if i = 0 or j = 0, \\ T [i - 1, j - 1] + 1 & if x_{i} = x_{j} and i \neq j, \\ max (T [i - 1, j], T [i, j - 1]) & otherwise . \end{cases}

$T[i,j] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\ \max(T[i-1,j],T[i,j-1]) & \text{otherwise}. \end{cases}$

T [n, n]

$T[n,n]$

jir17
sumber

Misalkan kita berada di beberapa dengan , dan kondisi dalam pernyataan Anda benar. Kemudian menyiratkan bahwa karakter pada posisi adalah bagian dari kedua berikutnya.

i, j

$i, j$

i = j + 1

$i=j+1$ ifdp[i][j] = dp[i - 1][j - 1] + 1

i - 1 = j

$i-1=j$

j_random_hacker

Selamat Datang di Ilmu Komputer! Harap singkirkan kode sumber dan ganti dengan gagasan, kode semu, dan argumen kebenaran. Lihat di sini dan di sini untuk diskusi meta terkait.

Raphael

@Raphael Formula rekursif tidak dihitung sebagai kode sumber.

Nomor 945

@BreakingBenjamin Tergantung pada bahasa pilihan Anda, Anda dapat menuliskan perulangan yang diberikan secara harfiah. Intinya adalah tidak ada penjelasan di sini.

Raphael

Menemukan pengulangan terpanjang

Jawaban: