Kleinste lexikografische Drehung eines Strings unter Verwendung von Suffix-Arrays in O (n)

Ich werde das Problem aus ACM 2003 zitieren:

Betrachten Sie eine Zeichenfolge mit der Länge n (1 <= n <= 100000). Bestimmen Sie die minimale lexikografische Rotation. Zum Beispiel sind die Rotationen der Zeichenfolge "Alabala":

Alabala

labalaa

abalaal

balaala

alaalab

Laalaba

aalabal

und der kleinste unter ihnen ist "aalabal".

Was die Lösung betrifft - ich weiß, dass ich ein Suffix-Array erstellen muss - und sagen wir, ich kann das in O (n) tun. Meine Frage ist immer noch, wie kann ich die kleinste Drehung in O (n) finden? (n = Länge eines Strings)

Ich bin sehr interessiert an diesem Problem und trotzdem bekomme ich irgendwie keine Lösung. Ich interessiere mich mehr für das Konzept und wie man das Problem löst und nicht für die konkrete Umsetzung.

Hinweis: Minimale Rotation bedeutet in der gleichen Reihenfolge wie in einem englischen Wörterbuch - "dwor" steht vor "word", weil d vor w steht.

EDIT: Suffix-Array-Konstruktion benötigt O (N)

LAST EDIT: Ich glaube ich habe eine Lösung gefunden !!! Was ist, wenn ich nur zwei Zeichenfolgen zusammengeführt habe? Wenn der String also "alabala" ist, würde der neue String "alabalaalabala" sein und jetzt würde ich einfach ein Suffix-Array davon erstellen (in O (2n) = O (n)) und das erste Suffix erhalten? Ich denke, das könnte richtig sein. Was denkst du? Vielen Dank!

Ein einfacher Trick, um alle Rotationen einer Zeichenfolge der Länge N zu konstruieren, besteht darin, die Zeichenfolge mit sich selbst zu verketten.

Dann ist jeder Teilstring mit N-Länge dieser Zeichenfolge mit 2N-Länge eine Drehung des ursprünglichen Strings.

Das Auffinden des "lexikographisch minimalen" Teilstrings erfolgt dann mit Ihrer O (N) -Baumkonstruktion.

Ich bin mir ziemlich sicher, dass die in einem Suffix-Array enthaltenen Informationen nicht ausreichen, um zu O (n) zu gelangen, aber höchstens zu O (n log n). Betrachten Sie diese Familie von Suffixen:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Sie konstruieren das nächste Suffix, indem Sie das vorherige Suffix (z. B. aba) verwenden, das nächste noch nicht verwendete Zeichen hinzufügen und dann das vorherige Suffix erneut hinzufügen (also aba -> aba c aba).

Betrachten Sie nun diese Zeichenfolgen (das Leerzeichen wird zur Hervorhebung hinzugefügt, ist jedoch nicht Teil der Zeichenfolge):

ad abacaba
bd abacaba
cd abacaba

Für diese drei Zeichenfolgen sieht der Anfang des Suffix-Arrays folgendermaßen aus:

a
aba
abacaba
(other suffixes)

Kommt mir bekannt vor? Diese Zeichenfolgen sind natürlich darauf zugeschnitten, dieses Suffix-Array zu erstellen. Abhängig vom Anfangsbuchstaben (a, b oder c) ist der 'richtige' Index (die Lösung für Ihr Problem) entweder das erste, das zweite oder das dritte Suffix in der obigen Liste.

Die Wahl des ersten Buchstabens wirkt sich kaum auf das Suffix-Array aus. Dies hat insbesondere keinen Einfluss auf die Reihenfolge der ersten drei Suffixe im Suffix-Array. Dies bedeutet, dass wir log n Zeichenfolgen haben, für die das Suffix-Array extrem ähnlich ist, der 'richtige' Index jedoch sehr unterschiedlich ist.

Obwohl ich keinen harten Beweis habe, deutet dies stark darauf hin, dass Sie keine andere Wahl haben, als die Rotationen, die diesen ersten drei Indizes im Array entsprechen, auf ihre lexikografische Reihenfolge zu vergleichen, was wiederum bedeutet, dass Sie mindestens O (n) benötigen log n) Zeit dafür (da die Anzahl der alternativen ersten Zeichen - in unserem Fall 3 - log n ist und der Vergleich zweier Zeichenfolgen O (n) Zeit benötigt).

Dies schließt die Möglichkeit eines O (n) -Algorithmus nicht aus. Ich habe nur Zweifel, dass ein Suffix-Array Ihnen dabei hilft, diese Laufzeit zu erreichen.

Die kleinste Drehung beginnt mit einem Teil des Suffixes aus dem Suffix-Array. Suffixe sind lexikographisch geordnet. Dies gibt Ihnen einen großen Starthilfe:

• Sie wissen, dass Sie fertig sind (ab dem ersten) , wenn Sie ein solches k erhalten, dass die Rotation, die mit dem Suffix k beginnt, kleiner ist als die Rotation, die mit dem Suffix k +1 beginnt.
• Sie können den Vergleich von "Drehung beginnend mit dem Suffix k ist kleiner als Drehung beginnend mit dem Suffix k +1" in O (1) durchführen, indem Sie die Länge der Suffixe vergleichen und optional ein Zeichen mit einem anderen Zeichen vergleichen.

BEARBEITEN: "Ein Zeichen mit einem anderen Zeichen" ist möglicherweise nicht immer so, es kann mehr als ein Zeichen sein, aber insgesamt untersuchen Sie während des gesamten Suchvorgangs nicht mehr als n Zeichen, also ist es O (n).

Kurzer Beweis: Sie untersuchen Zeichen nur, wenn das Suffix k +1 länger als das Suffix k ist , und Sie halten an und finden Ihre Lösung, wenn das Suffix k +1 kürzer als das Suffix k ist (dann wissen Sie, dass das Suffix k das ist, nach dem Sie gesucht haben). Sie untersuchen Zeichen also nur, wenn Sie sich in einer steigenden (Längen-) Folge von Suffixen befinden. Da Sie nur überschüssige Zeichen untersuchen, können Sie nicht mehr als n Zeichen untersuchen.

EDIT2: Dieser Algorithmus basiert auf der Tatsache, dass "wenn das Suffix-Array zwei Nachbarsuffixe enthält und das vorherige kürzer als das nachfolgende ist, das vorherige das Präfix des nachfolgenden ist". Wenn dies nicht wahr ist, dann tut mir leid.

EDIT3: Nein, es gilt nicht. "abaaa" hat die Suffix-Tabelle "a", "aa", "aaa", "abaaa", "baaa". Aber vielleicht kann dieser Gedankengang letztendlich zur Lösung führen, nur einige Details müssen verfeinert werden. Die Hauptfrage ist, ob es möglich ist, den oben genannten Vergleich irgendwie durchzuführen, indem weniger Zeichen untersucht werden. Es ist also O (n) total, was ich irgendwie für möglich halte. Ich kann jetzt einfach nicht sagen wie.

Problem:

Lexikographisch am wenigsten kreisförmiger Teilstring ist das Problem, die Rotation einer Saite zu finden, die die niedrigste lexikographische Ordnung aller dieser Rotationen besitzt. Zum Beispiel wäre die lexikographisch minimale Rotation von "bbaaccaadd" "aaccaaddbb".

Lösung:

Ein AO (n) -Zeitalgorithmus wurde von Jean Pierre Duval (1983) vorgeschlagen.

Bei zwei Indizes iund jvergleicht Duvals Algorithmus Stringsegmente mit einer Länge j - iab iund j(als "Duell" bezeichnet ). Wenn index + j - igrößer als die Länge der Zeichenfolge ist, wird das Segment durch Umwickeln gebildet.

Betrachten Sie zum Beispiel s = "baabbaba", i = 5 und j = 7. Da j - i = 2 ist, ist das erste Segment, das bei i = 5 beginnt, "ab". Das zweite Segment, das bei j = 7 beginnt, wird durch Umwickeln konstruiert und ist ebenfalls "ab". Wenn die Zeichenfolgen wie im obigen Beispiel lexikografisch gleich sind, wählen wir diejenige, die bei i beginnt, als Gewinner, dh i = 5.

Der obige Vorgang wurde wiederholt, bis wir einen einzigen Gewinner haben. Wenn die Eingabezeichenfolge ungerade ist, gewinnt das letzte Zeichen ohne Vergleich in der ersten Iteration.

Zeitliche Komplexität:

Die erste Iteration vergleicht jeweils n Zeichenfolgen der Länge 1 (n / 2 Vergleiche), die zweite Iteration kann n / 2 Zeichenfolgen der Länge 2 (n / 2 Vergleiche) usw. vergleichen, bis die i-te Iteration 2 Zeichenfolgen von vergleicht Länge n / 2 (n / 2 Vergleiche). Da sich die Anzahl der Gewinner jedes Mal halbiert, beträgt die Höhe des Rekursionsbaums log (n), wodurch wir einen O (n log (n)) - Algorithmus erhalten. Für kleines n ist dies ungefähr O (n).

Die Raumkomplexität ist ebenfalls O (n), da in der ersten Iteration n / 2 Gewinner, in der zweiten Iteration n / 4 Gewinner usw. gespeichert werden müssen. (Wikipedia behauptet, dass dieser Algorithmus konstanten Raum verwendet, ich verstehe nicht wie).

Hier ist eine Scala-Implementierung. Sie können jederzeit in Ihre bevorzugte Programmiersprache konvertieren.

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)
}

Ich sehe nichts besseres als O (N²).

Wenn Sie eine Liste mit N ganzen Zahlen haben, können Sie die kleinste in O (N) -Vergleichen auswählen.

Hier haben Sie eine Liste von N Zeichenfolgen der Größe N (deren Erstellung kostet nichts, eine Zeichenfolge wird vollständig durch ihren Startindex bestimmt). Sie können die kleinste in O (N) Vergleichen auswählen. Aber jeder Vergleich ist O (N) Grundoperationen. Die Komplexität ist also O (N²).