Das Problem ist leicht zu erklären: Wir haben zwei große Arrays (32-Bit-Integer-Werte) und wir müssen alle gängigen Sequenzen oberhalb einer bestimmten Anzahl von aufeinanderfolgenden Positionen (n) finden.
Wenn zum Beispiel n = 3 und zu vergleichende Arrays sind:
%Vor%Das algoritmh sollte zwei Arrays zurückgeben:
%Vor%(oder besser, seine relativen Positionen zum ersten Array und die Anzahl aufeinander folgender Bytes).
Ich glaube, ein guter Punkt ist der längste gemeinsame Teilstring-Algorithmus , aber vielleicht kennt jemand einen Algorithmus, der besser passt oder genau mit meinem Problem.
Ich denke, dass der Algorithmus zum Finden von LCS unter Verwendung des Suffixbaums eine perfekte Anpassung ist. Sie erstellen den Suffixbaum auf die gleiche Weise, aber in der letzten Phase suchen Sie nicht nach dem tiefsten Knoten, der Nachkommen für beide Strings hat. Sie suchen nach allen Knoten mit einer Tiefe von mehr als n , die für beide Zeichenfolgen Nachkommen haben.
Ich denke, die Algorithmen auf der Wikipedia-Seite, auf die Sie verweisen, machen fast genau das, was Sie wollen. Sie müssen sie nur ändern, um alle Antworten über eine bestimmte Größe zu halten, anstatt nur die längste Antwort zu behalten. Zum Beispiel könnte die dynamische Programmierlösung auf dieser Seite wie folgt geändert werden:
%Vor%Wie bereits erwähnt, enthält dies sowohl Präfixe als auch längste Übereinstimmungen. Diese könnten herausgefiltert werden, indem man nachspürt, welche Zeichenkette in L gefunden wurde, und ein Präfix aus der Rückkehrmenge entfernen, wenn wir feststellen, dass es eine Erweiterung hat.
Tags und Links algorithm