Ich kenne LCS-Algorithmen für 2 Strings. Suchen nach Vorschlägen zum Auffinden von gemeinsamen Teilstrings in 2..N-Strings. Es kann mehrere gemeinsame Teilstrings in jedem Paar geben. In Teilmengen der Strings kann es verschiedene gemeinsame Teilstrings geben.
strings: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)
gemeinsame Zeichenfolgen:
%Vor%längste gemeinsame Strings:
%Vor%am häufigsten verwendeten Zeichenfolgen:
%Vor%So etwas wird in der DNA-Sequenzanalyse immer gemacht. Sie können eine Vielzahl von Algorithmen dafür finden. Eine vernünftige Sammlung ist hier aufgeführt.
Es gibt auch den Brute-Force-Ansatz, Tabellen von jeder Teilfolge zu machen (wenn Sie nur an kurzen interessiert sind): Bilden Sie einen N-ären Baum (N = 26 für Buchstaben, 256 für ASCII) auf jeder Ebene und speichert Histogramme der Zählung an jedem Knoten. Wenn Sie wenig genutzte Knoten abschneiden (um die Speicheranforderungen vernünftig zu halten), erhalten Sie einen Algorithmus, der alle Untersequenzen mit einer Länge bis zu M in etwa N * M ^ 2 * log (M) Zeit für die Eingabe der Länge findet N. Wenn Sie dies stattdessen in K separate Strings aufteilen, können Sie die Baumstruktur erstellen und einfach die Antwort (en) in einem einzigen Durchlauf durch den Baum ablesen.
Suffix-Bäume sind die Antwort, es sei denn, Sie haben wirklich große Strings, bei denen der Speicher zum Problem wird. Erwarten Sie für eine gute Implementierung 10 ~ 30 Byte Speicherbelegung pro Zeichen in der Zeichenfolge. Es gibt auch einige Open-Source-Implementierungen, die Ihre Arbeit erleichtern.
Es gibt auch andere, mehr Sucintalgorithmen, aber sie sind schwieriger zu implementieren (suchen Sie nach "komprimierten Suffixbäumen").