Ich versuche, dieses Problem in spoj
zu lösenIch muss die Anzahl der Umdrehungen einer gegebenen Saite finden, die sie lexikographisch am kleinsten unter allen Rotationen macht.
Zum Beispiel:
Original: ama
Erste Rotation: maa
Zweite Drehung: aam Dies ist die lexikographisch kleinste Drehung, also ist die Antwort 2.
Hier ist mein Code:
%Vor%Ich bekomme "Zeitlimit überschritten" für diese Lösung. Ich verstehe nicht, welche Optimierungen gemacht werden können. Wie kann ich die Geschwindigkeit meiner Lösung erhöhen?
Sie können ein modifiziertes Suffix-Array verwenden. Ich meine geändert, weil Sie nicht am Wortende aufhören müssen.
Hier ist der Code für ein ähnliches Problem , das ich gelöst habe (SA ist das Suffix-Array):
%Vor%Ich habe diese Implementierung hauptsächlich von übernommen Buch . Es gibt eine leichter zu schreibende O (n log²n) Version, aber möglicherweise nicht effizient genug für Ihren Fall (n = 10 ^ 5). Diese Version ist O (n log n), und es ist nicht der effizienteste Algorithmus. Der wikipedia-Artikel listet einige O (n) -Algorithmen auf, aber ich finde die meisten von ihnen zu komplex, um sie während eines Programmierwettbewerbs zu schreiben. Dieses O (n log n) ist normalerweise für die meisten Probleme ausreichend.
Sie können einige Folien finden, die Suffix-Array-Konzept erklären (von dem Autor des Buches, das ich erwähnte) hier .
Ich weiß, das kommt sehr spät, aber ich stolperte über Google auf meiner Suche nach einer noch schnelleren Variante dieses Algorithmus. Es stellte sich heraus, dass eine gute Implementierung bei github gefunden wurde: Ссылка
Es verwendet die Lyndon-Faktorisierung. Das bedeutet, dass es die Zeichenfolge wiederholt in lexikografisch abnehmende Lyndonwörter aufteilt. Lyndon Wort sind Strings, die (eine der) minimalen Rotationen von sich selbst sind. Wenn Sie dies kreisförmig tun, erhalten Sie die lms der Saite als das letzte gefundene Lyndon-Wort.
%Vor%Tags und Links algorithm string c++ lexicographic