Kürzeste sich wiederholende Teilzeichenkette

Question

Ich suche nach einer effizienten Möglichkeit, die kürzeste sich wiederholende Teilzeichenkette zu extrahieren. Zum Beispiel:

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

Ich würde mich über jede Antwort oder Information zu diesem Problem freuen.

Auch in diese Stelle wird vorgeschlagen, den regulären Ausdruck wie folgt zu verwenden

re=^(.*?)\1+$

um das kleinste sich wiederholende Muster in der Zeichenkette zu finden. Aber ein solcher Ausdruck funktioniert nicht in Python und gibt mir immer eine Nicht-Übereinstimmung zurück (ich bin neu in Python und vielleicht übersehe ich etwas?).

--- weiterverfolgen ---

Hier besteht das Kriterium darin, das kürzeste nicht überlappende Muster zu suchen, dessen Länge größer als eins ist und das die größte Gesamtlänge hat.

Answer 1

Eine schnelle Lösung für dieses Muster könnte sein

(.+?)\1+

Ihre Regex ist fehlgeschlagen, weil sie die sich wiederholende Zeichenfolge am Anfang und am Ende der Zeile verankert und nur Zeichenfolgen wie abcabcabc aber nicht xabcabcabcx . Außerdem sollte die Mindestlänge der wiederholten Zeichenfolge 1 und nicht 0 sein (sonst würde jede beliebige Zeichenfolge passen). .+? 代わりに .*? .

In Python:

>>> import re
>>> r = re.compile(r"(.+?)\1+")
>>> r.findall("cbabababac")
['ba']
>>> r.findall("dabcdbcdbcdd")
['bcd']

Beachten Sie jedoch, dass diese Regex nur nicht überlappende, sich wiederholende Übereinstimmungen findet, so dass im letzten Beispiel die Lösung d wird nicht gefunden, obwohl dies die kürzeste sich wiederholende Zeichenfolge ist. Oder sehen Sie sich dieses Beispiel an: hier kann es nicht gefunden werden abcd weil die abc Teil des ersten abcd ist im ersten Spiel verbraucht worden):

>>> r.findall("abcabcdabcd")
['abc']

Außerdem kann es mehrere Treffer geben, so dass Sie in einem zweiten Schritt den kürzesten finden müssen:

>>> r.findall("abcdabcdabcabc")
['abcd', 'abc']

Eine bessere Lösung:

Damit die Maschine auch überlappende Übereinstimmungen finden kann, verwenden Sie

(.+?)(?=\1)

Dadurch werden einige Zeichenketten zweimal oder öfter gefunden, wenn sie oft genug wiederholt werden, aber es werden mit Sicherheit alle möglichen sich wiederholenden Teilzeichenketten gefunden:

>>> r = re.compile(r"(.+?)(?=\1)")
>>> r.findall("dabcdbcdbcdd")
['bcd', 'bcd', 'd']

Daher sollten Sie die Ergebnisse nach Länge sortieren und das kürzeste Ergebnis zurückgeben:

>>> min(r.findall("dabcdbcdbcdd") or [""], key=len)
'd'

En or [""] (Dank an J. F. Sebastian!) gewährleistet, dass keine ValueError wird ausgelöst, wenn es überhaupt keine Übereinstimmung gibt.

Answer 2

^ passt auf den Anfang einer Zeichenkette. In Ihrem Beispiel beginnen die sich wiederholenden Teilzeichenfolgen nicht am Anfang. Ähnlich bei $ . Ohne ^ y $ das Muster .*? findet immer eine leere Zeichenkette. Demo :

import re

def srp(s):
    return re.search(r'(.+?)\1+', s).group(1)

print srp('dabcdbcdbcdd') # -> bcd
print srp('cbabababac')   # -> ba

Es findet jedoch nicht die kürzeste Teilzeichenkette.