Rotasi leksikografis terkecil dari string menggunakan susunan sufiks dalam O (n)

Saya akan mengutip masalah dari ACM 2003:

Pertimbangkan string dengan panjang n (1 <= n <= 100000). Tentukan rotasi leksikografis minimumnya. Misalnya, rotasi string "alabala" adalah:

alabala

labalaa

abalaal

balaala

alaalab

laaba

aalabal

dan yang terkecil di antara mereka adalah "aalabal".

Adapun solusinya - saya tahu saya perlu membangun array suffix - dan katakanlah saya bisa melakukannya di O (n). Pertanyaan saya masih, bagaimana saya bisa menemukan rotasi terkecil di O (n)? (n = panjang string)

Saya sangat tertarik dengan masalah ini dan saya masih belum mendapatkan solusinya. Saya lebih tertarik pada konsep dan bagaimana menyelesaikan masalah dan bukan pada implementasi konkret.

Catatan: rotasi minimum berarti dalam urutan yang sama seperti dalam kamus bahasa Inggris - "dwor" adalah sebelum "kata" karena d adalah sebelum w.

EDIT: konstruksi array suffix membutuhkan O (N)

EDIT TERAKHIR: Saya pikir saya menemukan solusinya !!! Bagaimana jika saya baru saja menggabungkan dua string? Jadi jika string adalah "alabala" string baru akan saya "alabalaalabala" dan sekarang saya hanya akan membangun array sufiks ini (di O (2n) = O (n)) dan mendapatkan sufiks pertama? Saya kira ini mungkin benar. Bagaimana menurut anda? Terima kasih!

Trik sederhana untuk membuat semua rotasi string dengan panjang N adalah menggabungkan string dengan dirinya sendiri.

Maka setiap substring N-length dari string 2N-length ini adalah rotasi dari string asli.

Menemukan substring "minimal leksikografis" kemudian dilakukan dengan konstruksi pohon O (N) Anda.

Saya cukup yakin informasi yang terkandung dalam array suffix tidak cukup untuk membantu Anda mencapai O (n), tetapi paling banyak dapat membantu Anda ke O (n log n). Pertimbangkan keluarga sufiks ini:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Anda membuat sufiks berikutnya dengan mengambil sufiks sebelumnya (mis. Aba), menambahkan karakter berikutnya yang belum digunakan dan kemudian menambahkan sufiks sebelumnya lagi (jadi aba -> aba c aba).

Sekarang perhatikan string ini (spasi ditambahkan untuk penekanan, tetapi bukan bagian dari string):

ad abacaba
bd abacaba
cd abacaba

Untuk tiga string ini, awal array suffix akan terlihat seperti ini:

a
aba
abacaba
(other suffixes)

Terlihat tidak asing? String ini tentu saja dirancang untuk membuat susunan sufiks ini. Sekarang, tergantung pada huruf awal (a, b atau c), indeks 'benar' (solusi untuk masalah Anda) adalah sufiks pertama, kedua atau ketiga dalam daftar di atas.

Pilihan huruf pertama hampir tidak mempengaruhi array suffix; khususnya, itu tidak mempengaruhi urutan dari tiga sufiks pertama dalam array sufiks. Ini berarti bahwa kita memiliki string n log yang array sufiksnya sangat mirip tetapi indeks 'benar' sangat berbeda.

Meskipun saya tidak punya bukti keras, ini sangat menyarankan saya bahwa Anda tidak punya pilihan selain membandingkan rotasi sesuai dengan tiga indeks pertama dalam array untuk pemesanan leksikografis mereka, yang pada gilirannya berarti bahwa Anda akan memerlukan setidaknya O (n log n) waktu untuk ini (karena jumlah karakter pertama alternatif - dalam kasus kami 3 - adalah log n, dan membandingkan dua string membutuhkan O (n) waktu).

Ini tidak mengesampingkan kemungkinan algoritma O (n). Saya hanya ragu bahwa susunan sufiks membantu Anda dalam mencapai waktu berjalan ini.

Rotasi terkecil adalah yang dimulai dengan beberapa suffix dari array suffix. Sufiks dipesan secara leksikografis. Ini memberi Anda lompatan besar:

• Anda tahu bahwa begitu Anda mendapatkan k sehingga rotasi dimulai dengan suffix k lebih kecil dari rotasi dimulai dengan suffix k +1, Anda selesai (mulai dari yang pertama);
• Anda dapat melakukan perbandingan "rotasi dimulai dengan sufiks k lebih kecil dari rotasi dimulai dengan sufiks k +1" dalam O (1) dengan membandingkan panjang sufiks dan secara opsional, membandingkan satu karakter dengan karakter lainnya.

EDIT: "satu karakter dengan satu karakter lain" mungkin tidak selalu demikian, mungkin lebih dari satu karakter, tetapi secara keseluruhan, Anda tidak memeriksa lebih dari n karakter melalui seluruh proses pencarian, jadi itu adalah O (n).

Bukti singkat: Anda hanya memeriksa karakter ketika sufiks k +1 lebih panjang dari sufiks k , dan Anda berhenti dan menemukan solusi Anda jika sufiks k +1 lebih pendek dari sufiks k (maka Anda tahu sufiks k adalah yang Anda cari). Jadi, Anda hanya memeriksa karakter saat Anda berada dalam urutan sufiks yang meningkat (panjang-bijaksana). Karena Anda hanya memeriksa kelebihan karakter, Anda tidak dapat memeriksa lebih dari n karakter.

EDIT2: Algoritma ini bergantung pada fakta "jika ada dua sufiks tetangga dalam array sufiks dan yang sebelumnya lebih pendek dari yang berikutnya, yang sebelumnya adalah awalan dari yang berikutnya". Jika ini tidak benar, maka maaf.

EDIT3: Tidak, itu tidak berlaku. "abaaa" memiliki tabel suffix "a", "aa", "aaa", "abaaa", "baaa". Tapi mungkin garis pemikiran ini pada akhirnya dapat mengarah pada solusi, hanya beberapa detail yang lebih canggih. Pertanyaan utamanya adalah apakah mungkin untuk membuat perbandingan yang disebutkan di atas dilakukan dengan memeriksa lebih sedikit karakter, jadi itu adalah O (n) sepenuhnya, yang entah bagaimana saya percaya mungkin saja terjadi. Aku tidak tahu bagaimana caranya, sekarang.

Masalah:

Substring paling tidak leksikografis adalah masalah menemukan rotasi string yang memiliki urutan leksikografis terendah dari semua rotasi tersebut. Misalnya, rotasi minimal leksikografis "bbaaccaadd" akan menjadi "aaccaaddbb".

Larutan:

Algoritma waktu AO (n) diusulkan oleh Jean Pierre Duval (1983).

Diberikan dua indeks idan j, algoritma Duval membandingkan segmen string dengan panjang j - imulai dari idan j(disebut "duel" ). Jika index + j - ilebih besar dari panjang tali, ruas ini dibentuk dengan membungkusnya.

Sebagai contoh, perhatikan s = "baabbaba", i = 5 dan j = 7. Karena j - i = 2, segmen pertama dimulai dari i = 5 adalah "ab". Segmen kedua mulai dari j = 7 dibangun dengan membungkus, dan juga "ab". Jika string secara leksikografis sama, seperti dalam contoh di atas, kita memilih yang dimulai dari i sebagai pemenang, yaitu i = 5.

Proses di atas berulang hingga kami memiliki satu pemenang. Jika string input panjangnya aneh, karakter terakhir menang tanpa perbandingan dalam iterasi pertama.

Kompleksitas waktu:

Iterasi pertama membandingkan n string setiap panjang 1 (perbandingan n / 2), iterasi kedua dapat membandingkan n / 2 string dengan panjang 2 (n / 2 perbandingan), dan seterusnya, hingga iterasi ke-2 membandingkan 2 string dari panjang n / 2 (perbandingan n / 2). Karena jumlah pemenang dibelah dua setiap kali, ketinggian pohon rekursi adalah log (n), sehingga memberi kita algoritma O (n log (n)). Untuk n kecil, ini kira-kira O (n).

Kompleksitas ruang juga O (n), karena dalam iterasi pertama, kita harus menyimpan n / 2 pemenang, iterasi kedua n / 4 pemenang, dan seterusnya. (Wikipedia mengklaim algoritma ini menggunakan ruang konstan, saya tidak mengerti caranya).

Inilah implementasi Scala; jangan ragu untuk mengonversi ke bahasa pemrograman favorit Anda.

def lexicographicallyMinRotation(s: String): String = {
 @tailrec
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             }
             .reduce((a, b) => if (a._2 <= b._2) a else b)
             ._1
         case xs => xs.head
       }
       .toSeq
     duel(newWinners)
   }
 }

 duel(s.indices)
}

Saya tidak melihat sesuatu yang lebih baik daripada O (N²).

Jika Anda memiliki daftar bilangan bulat N, Anda dapat memilih perbandingan terkecil dalam O (N).

Di sini Anda memiliki daftar string N ukuran N (membangun mereka tanpa biaya, string sepenuhnya ditentukan oleh indeks awal). Anda dapat memilih yang terkecil dalam perbandingan O (N). Tetapi setiap perbandingan adalah operasi dasar O (N). Jadi kompleksitasnya adalah O (N²).