Vorgegebene n Zeichenfolge mit maximaler Länge m. Wie können wir das längste gemeinsame Präfix finden, das mindestens zwei Zeichenfolgen gemeinsam haben?
Beispiel: ['flower', 'flow', 'hallo', 'Flotte']
Antwort: fl
Ich dachte daran, für die ganze Zeichenfolge ein Trie zu erstellen und dann den tiefsten Knoten zu prüfen (erfüllt den längsten), der sich zu zwei / mehr Teilstrings verzweigt (erfüllt die Gemeinsamkeit). Dies benötigt O (n * m) Zeit und Raum. Gibt es einen besseren Weg, dies zu tun?
Es gibt eine O(|S|*n) Lösung für dieses Problem, indem Sie trie verwenden. [ n ist die Anzahl der Zeichenfolgen, S ist die längste Zeichenfolge]
Es gibt keine schnellere Lösung als in der großen O-Notation, im schlimmsten Fall sind alle Strings identisch - und Sie müssen alle lesen, um es zu wissen.
Warum sollte man trie verwenden (was O (mn) Zeit und O (mn) Raum braucht, einfach die Brute-Force-Methode verwenden. erste Schleife, finde die kürzeste Zeichenfolge als minStr, die o (n) Zeit braucht, zweite Schleife , vergleichen Sie eins nach dem anderen mit diesem minStr, und behalten Sie eine Variable, die den ganz rechten Index von minStr angibt, diese Schleife nimmt O (mn), wobei m die kürzeste Länge aller Strings ist. Der Code ist wie folgt,
%Vor% Ich würde sie sortieren, was Sie in n lg n time tun können. Dann werden alle Strings mit gemeinsamen Präfixen direkt nebeneinander stehen. Tatsächlich sollten Sie in der Lage sein, einen Zeiger auf den Index zu halten, den Sie gerade betrachten, und sich für eine ziemlich schnelle Berechnung nach unten arbeiten.
Als eine ganz andere Antwort als meine andere Antwort ...
Sie können mit einem Durchlauf jede Zeichenkette basierend auf ihrem ersten Buchstaben gruppieren.
Mit einem weiteren Durchlauf können Sie jeden Bucket basierend auf seiner Sekunde sortieren. (Dies wird als Radix-Sortierung bezeichnet, die bei jedem Durchlauf O(n*m) und O(n) ist.) Dies ergibt ein Basispräfix von 2.
Sie können Elemente, die kein Präfix 2 haben, sicher aus Ihrem Dataset entfernen.
Sie können die Radix-Sortierung fortsetzen, indem Sie Elemente ohne ein gemeinsames Präfix von p als p approaches m entfernen.
Dies gibt Ihnen die gleiche O(n*m) -Zeit, die der Trie-Ansatz hat, ist aber immer schneller als der Trie, da der Trie jedes Zeichen in jeder Zeichenkette betrachten muss (während er in die Struktur eintritt), während dieser Ansatz ist nur garantiert, um 2 Zeichen pro String zu sehen, an welchem Punkt es einen Großteil des Datasets aussortiert.
Der schlechteste Fall ist immer noch, dass jeder String identisch ist, weshalb er die gleiche große O-Notation teilt, aber in allen Fällen schneller ist, da garantiert weniger Vergleiche verwendet werden, als in irgendeinem "Nicht-Worst-Case" sind Charaktere, die nie besucht werden müssen.
Es kommt vor, dass die durch corsiKa beschriebene Bucket-Sortierung (Radix-Sortierung) so erweitert werden kann, dass alle Strings irgendwann alleine in einem Bucket platziert werden, und an dieser Stelle ist das LCP für solch eine einsame Saite bekannt. Ferner ist auch das Schütteln jeder Saite bekannt; es ist länger als das LCP. Die Bucket-Sortierung ist defacto die Konstruktion eines Suffix-Arrays, aber nur teilweise. Diese Vergleiche, die nicht durchgeführt werden (wie von corsiKa beschrieben), repräsentieren tatsächlich jene Teile der Suffix-Strings, die nicht zu dem Suffix-Array hinzugefügt sind. Schließlich ermöglicht diese Methode nicht nur die Bestimmung des LCP und der Shustrings, sondern auch die Suche nach Teilsequenzen, die nicht in der Zeichenkette enthalten sind.
Da die Welt offensichtlich in Swift um eine Antwort bettelt, hier ist meins;)
%Vor%Swift 3 Update:
%Vor%Was ist interessant zu beachten:
Grapheme Clusters , was der Character -Typ darstellt. Und die Funktion gegeben, die ich brauchte, um an erster Stelle zu schreiben:
%Vor%Hier ist ein minimaler Komponententest:
%Vor%Tags und Links algorithm