Was ist die beste Datenstruktur und der beste Algorithmus zum Vergleich einer Liste von Zeichenfolgen?

Question

Ich möchte die längstmögliche Abfolge von Wörtern finden, die den folgenden Regeln entsprechen:

• Jedes Wort kann höchstens einmal verwendet werden
• Alle Wörter sind Saiten
• Zwei Saiten sa und sb kann verkettet werden, wenn die letzten beiden Zeichen von sa entspricht den ersten beiden Zeichen von sb.

Im Falle einer Verkettung wird es durch Überlappung dieser Charaktere durchgeführt. Zum Beispiel:

• Sa = "Torino"
• SB = "Novara"
• sa concat sb = "torinovara"

Zum Beispiel habe ich die folgende Eingabedatei "input.txt":

Novara

Torino

Vercelli

Ravenna

Napoli

Liverno

Messanien

Noviligur

Roma

Und die Ausgabe der obigen Datei gemäß den oben genannten Regeln sollte sein:

Torino

Novara

Ravenna

Napoli

Livorno

Noviligur

Da die längstmögliche Verkettung ist:

torinovaravennapolivornovilligure

Kann mir bitte jemand dabei helfen? Was wäre die beste Datenstruktur dafür?

Answer 1

Dies kann als gerichtetes Graphenproblem dargestellt werden-die Knoten sind Wörter und sie sind durch eine Kante verbunden, wenn sie sich überlappen .

(Nun, eigentlich möchten Sie das Diagramm ein wenig erweitern, um den Beginn und das Ende eines Wortes zu bearbeiten. Gehen Sie mit einem "Startknoten" mit einer Kante zu jedem Wort mit Gewichtslänge. + Länge Finish / 2 und zwischen jedem Wort und einem "Endknoten" "Längenword / 2". Möglicherweise ist es einfacher, es zu verdoppeln.)

https://csthory.stackexchange.com/questions/3684/max-non-overlaping-path-in-weighted-graph

Answer 2

Ich würde wirklich einfach anfangen. Machen Sie 2 Vektoren von Saiten, die normal sortiert sind und eine nach den letzten 2 Buchstaben sortiert. Erstellen Sie einen Index (Vektor der INTs) für den zweiten Vektor, der darauf hinweist, dass er in der ersten Position ist.

Um die längste zu finden. Entfernen Sie zuerst die Waisen. Wörter, die an beiden Enden nicht übereinstimmen. Dann willst du a bauen Nachbar beitragen Baum, hier bestimmen Sie, welche Wörter sich möglicherweise erreichen können. Wenn Sie 2 oder mehr Bäume haben, sollten Sie zuerst den größten Baum ausprobieren.

Mit einem Baum ist es Ihre Aufgabe, seltene Ziele zu finden, an andere Enden zu binden und zu wiederholen. Dies sollte Ihnen eine ziemlich schöne Lösung bekommen, wenn alle Wörter Ihre goldenen verwendet, überspringen Sie die anderen Bäume. Wenn dies nicht der Fall ist, sind Sie in eine ganze Reihe von Algorithmen, um dies effizient zu machen.

Einige zu berücksichtigende Elemente: Wenn Sie 3+ eindeutige Enden haben, wird garantiert 1+ Wörter fallen. Dies kann verwendet werden, um Ihre Versuche bei der Suche nach einer Antwort zu beschneiden. Rechenung der einzigartigen Enden oft neu. Ungewöhnliche Anzahl eines bestimmten Endes Stellen Sie sicher, dass man fallen gelassen werden muss (Sie erhalten 2 Werbegeschenke an den Enden). Trennende Wörter, die sich selbst übereinstimmen können, Sie können sie immer in den letzten werfen, und sie mischen die Mathematik ansonsten. Möglicherweise können Sie kleine, selbst passtende Ringe erstellen. Sie können diese wie selbstsprechende Wörter behandeln, solange Sie sie nicht verwandeln, wenn Sie sie erstellen. Dies kann die Leistung fantastisch machen, aber keine Garantien für eine perfekte Lösung.

Der Suchraum ist Ordnung (n!) Eine Liste von Millionen von Elementen kann schwierig sein, eine genaue Antwort zu beweisen. Natürlich könnte ich etwas übersehen.