Algorithmus, um eine gemeinsame Teilfolge über N strings
Ich bin vertraut mit LCS-algorithmen für 2 Streicher. Auf der Suche nach Anregungen für die Suche nach gemeinsamen Teilstrings, der in 2..N strings. Es können mehrere common substrings in jedem paar. Es gibt verschiedene gemeinsame Teilstrings in Teilmengen von den Saiten.
Saiten: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)
gemeinsamen Saiten:
1/2 (DEF)
1/3 (ABCDEF)
1/4 (IJKL)
1/5 (FGH)
2/3 (DEF)
längsten gemeinsamen Zeichenketten:
1/3 (ABCDEF)
häufigsten strings:
1/2/3 (DEF)
- Ist es ein ACM-contest-problem, das erfordert Algorithmus mit bestimmter Leistung?
- Würde nicht den substring 'F' werden die häufigsten, wie es scheint, auf vier Saiten?
- Es wäre eine gute Idee, uns zu sagen, warum Sie dies benötigen, so können wir verstehen, wo wir gefährden kann und wo nicht.
- Römisch - ich bin kein student, und dies ist nicht für einen Wettbewerb :-). Die Anwendung ist auf der Suche nach gemeinsamen Elementen in ein PDF-Inhalte streamen. interjay - ich ignorierte einzelne Zeichen, Teilstrings
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Diese Art der Sache geschieht die ganze Zeit in der DNA-Sequenz-Analyse. Finden Sie eine Vielzahl von algorithmen für Sie. Eine vernünftige Auflistung aufgeführt ist hier.
Gibt es auch die brute-force-Ansatz der Tabellen von jeder substring (wenn Sie daran interessiert sind nur in die kurze): bilden einer N-ary tree (N=26 Buchstaben, 256 ASCII), die auf jeder Ebene und speichern Histogramme der Anzahl an jedem Knoten. Wenn Sie streichen Sie von wenig genutzten Knoten (halten die Speicher-Anforderungen angemessen), Sie am Ende mit einem Algorithmus, der findet alle untersequenzen der Länge bis M in so etwas wie N*M^2*log(M) Zeit für die Eingabe der Länge N. Wenn Sie stattdessen aufgeteilt in K separate Zeichenfolgen, Sie können beim Aufbau der Baumstruktur und einfach ablesen die Antwort(en) in einem einzelnen Durchlauf durch den Baum.
SUffix-Bäume sind die Antwort, es sei denn, Sie haben wirklich große strings, wo der Speicher zum problem wird. Erwarten 10~30 Byte Speicherverbrauch pro Zeichen in der Zeichenfolge für eine gute Umsetzung. Es gibt ein paar open-source-Implementierungen zu, die machen Ihre Arbeit leichter.
Gibt es andere, mehr succint algorithmen auch, aber Sie sind schwieriger zu implementieren (look für "compressed suffix-Bäume").