Suchen Sie das am längsten wiederholte Muster in einer Zeichenfolge

Ich suche nach einem effizienten Algorithmus, um das am längsten wiederholte Muster in einer Zeichenfolge zu finden.

Betrachten Sie beispielsweise die folgende Zahlenfolge:

5431428571428571428571428571427623874534.

Wie Sie sehen können, 142857142857ist dies das längste Muster, das in dieser Zeichenfolge einige Male (mindestens zweimal) wiederholt wird.

Die wiederholte Zeichenfolge sollte keine Idee enthalten, sondern Brute-Force?

algorithms strings subsequences Juho
quelle

Sie haben nicht definiert, was "ein paar Mal" bedeutet, aber wenn "zweimal" als "ein paar Mal" zählt, 142857ist es nicht das längste, weil 142857142857es länger ist. Ich denke, Sie sollten die Frage bearbeiten, um zu klären, was Sie unter „wiederholtem Muster“ verstehen.

Tsuyoshi Ito

sehr guter Punkt. Ich werde die Frage aktualisieren.

Müssen die Vorkommen des Musters voneinander getrennt sein? Denn wenn nicht, ist 142857142857 immer noch nicht die längste Wiederholung; 142857142857142857142 kommt zweimal vor. In jedem Fall lautet die übliche Antwort auf Fragen wie diese "Suffixbäume".

Antworten:

Das Problem ist überraschend nicht trivial. Zunächst zwei Brute-Force-Algorithmen. Ein Quadrat ("wiederholtes Muster") ist durch seine Länge $\ell$ und Position $p$ und benötigt Zeit $O(\ell)$ , um zu verifizieren. Wenn wir alle $\ell$ und $p$ durchgehen , erhalten wir einen $O(n^3)$ -Algorithmus. Wir können das verbessern, indem wir zuerst $\ell$ durchlaufen und dann den String mit zwei laufenden Zeigern in einem Abstand von $\ell$ scannen . Auf diese Weise kann überprüft werden, ob ein Quadrat der Länge $2\ell$ in linearer Zeit existiert, was eine Gesamtlaufzeit von ergibt $O(n^2)$ .

Kolpakov und Kucherov entwickelten einen Algorithmus zum Finden aller maximalen Wiederholungen in einem Wort in der Zeit $O(n)$ [1], und ihr Algorithmus kann verwendet werden, um alle maximalen Quadrate in der Zeit $O(n)$ . Eine Wiederholung ist ein Unterwort der Form $w^kx$ , wobei $k \geq 2$ und $x$ ein geeignetes Präfix von $w$ . Das größte in dieser Wiederholung enthaltene Quadrat ist $(w^{\lfloor k/2 \rfloor})^2$ . Mit dieser Formel kann man bei allen maximalen Wiederholungen in einem Wort (von denen es nur $O(n)$ viele gibt) das größte Quadrat finden.

[1] Kolpakov, R. & Kucherov, G. (1999). Maximale Wiederholungen in einem Wort in linearer Zeit finden . In Foundations of Computer Science, 1999. 40. Jährliches Symposium über (S. 596-604). IEEE.

Yuval Filmus
quelle