Wie kann ich feststellen, ob sich eine Zeichenfolge in Python wiederholt?

352

Ich suche nach einer Möglichkeit zu testen, ob sich eine bestimmte Zeichenfolge für die gesamte Zeichenfolge wiederholt oder nicht.

Beispiele:

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

sind Saiten, die sich wiederholen, und

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

sind Beispiele für diejenigen, die dies nicht tun.

Die sich wiederholenden Abschnitte der Zeichenfolgen, die mir gegeben werden, können ziemlich lang sein, und die Zeichenfolgen selbst können 500 oder mehr Zeichen umfassen. Daher scheint es furchtbar langsam, jedes Zeichen zu durchlaufen, um ein Muster zu erstellen, und dann das Muster mit dem Rest der Zeichenfolge zu vergleichen. Multiplizieren Sie das mit möglicherweise Hunderten von Zeichenfolgen, und ich sehe keine intuitive Lösung.

Ich habe mich ein wenig mit Regexen befasst und sie scheinen gut zu sein, wenn Sie wissen, wonach Sie suchen oder zumindest die Länge des Musters, das Sie suchen. Leider weiß ich auch nicht.

Wie kann ich feststellen, ob sich eine Zeichenfolge wiederholt und wenn ja, welche Subsequenz am kürzesten wiederholt wird?

John
quelle
15
Es scheint schrecklich langsam zu sein, jedes Zeichen zu durchlaufen, das versucht, ein Muster zu erstellen, und dann das Muster mit dem Rest der Zeichenfolge zu vergleichen - aber ist es das?
Tim
2
Mögliches Duplikat des Schreibens eines
Avinash Raj
2
@AvinashRaj Das ist nur ein Teil eines Strings, nicht die ganze Sache.
John
11
@AvinashRaj Das OP fragt nach allen möglichen Lösungen. Die Frage, auf die Sie verlinken, akzeptiert nur Regex- Lösungen. Beachten Sie, dass Regex das Problem möglicherweise lösen kann, jedoch in viel mehr Zeit als nötig. Zum Beispiel würde eine optimale Lösung (dh lineare Zeit) den Suffixbaum des Textes verwenden. Sie müssen nur die längste wiederholte Teilzeichenfolge finden und die Längen überprüfen.
Bakuriu
2
@ TigerhawkT3 Der reale Datensatz ist viel zu groß und unhandlich, aber die Beispiele in der Frage sind Teil davon, und wenn Sie möchten, hier noch einige .
John

Antworten:

570

Hier ist eine übersichtliche Lösung, die reguläre Ausdrücke und langsame In-Python-Schleifen vermeidet:

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

In der von @davidism gestarteten Community-Wiki-Antwort finden Sie Benchmark-Ergebnisse. Zusammenfassend,

Die Lösung von David Zhang ist der klare Gewinner und übertrifft alle anderen um mindestens das Fünffache des großen Beispielsatzes.

(Die Worte dieser Antwort, nicht meine.)

Dies basiert auf der Beobachtung, dass eine Zeichenfolge genau dann periodisch ist, wenn sie einer nichttrivialen Drehung von sich selbst entspricht. Ein großes Lob an @AleksiTorhamo für die Erkenntnis, dass wir dann die Hauptperiode aus dem Index des ersten Auftretens von sin wiederherstellen können (s+s)[1:-1], und für die Information über die Optionen startund endArgumente von Python string.find.

David Zhang
quelle
19
Sie können dies erweitern, um die kürzeste sich wiederholende Teilsequenz zu finden, indem Sie .find()oder .index()anstelle von inz. (s+s).find(s, 1, -1).
Aleksi Torhamo
11
Ich denke auch, dass (s+s).find(s, 1, -1)es (sehr geringfügig) schneller sein wird als (s+s)[1:-1].find(s)zumindest bei größeren Saiten, da das Schneiden bedeutet, dass Sie eine weitere Kopie (fast) der gesamten Saite erstellen müssen.
Aleksi Torhamo
13
Es ist so, als würde man eine Sinus- oder Cos-Welle aus einer periodischen Funktion nehmen und nach rechts verschieben. Da es vollständig periodisch ist, werden die Wellen schließlich perfekt zusammenpassen ... Die mathematischen Parallelen zu dieser Lösung sind einfach phänomenal. :) Ich wünschte, ich könnte dir + ∞ Upvotes geben.
Shashank
6
Guidos jüngstes Update auf PEP 8 ist hier relevant: "Seien Sie in return-Anweisungen konsistent. Entweder sollten alle return-Anweisungen in einer Funktion einen Ausdruck zurückgeben, oder keine von ihnen sollte. Wenn eine return-Anweisung einen Ausdruck zurückgibt, alle return-Anweisungen, bei denen kein Wert vorhanden ist return sollte dies explizit als return None angeben, und am Ende der Funktion sollte eine explizite return-Anweisung vorhanden sein (falls erreichbar). "
Zero Piraeus
8
@WayneConrad Nehmen Sie beispielsweise eine Zeichenfolge, "abcd"lassen Sie das Zeichen rechts ab und kleben Sie es wieder links an, um es zu erhalten "dabc". Diese Prozedur wird als Drehen einer Zeichenfolge um 1 Zeichen nach rechts bezeichnet . Wiederholen Sie die nSchritte, um eine Zeichenfolge um nZeichen nach rechts zu drehen . Beachten Sie nun, dass bei einer Zeichenfolge k, die durch ein beliebiges Vielfaches nach rechts gedreht wird, kdie Zeichenfolge unverändert bleibt. Eine nichttriviale Drehung einer Zeichenfolge ist eine, deren Zeichennummer kein Vielfaches der Länge der Zeichenfolge ist.
David Zhang
181

Hier ist eine Lösung mit regulären Ausdrücken.

import re

REPEATER = re.compile(r"(.+?)\1+$")

def repeated(s):
    match = REPEATER.match(s)
    return match.group(1) if match else None

Durchlaufen der Beispiele in der Frage:

examples = [
    '0045662100456621004566210045662100456621',
    '0072992700729927007299270072992700729927',
    '001443001443001443001443001443001443001443',
    '037037037037037037037037037037037037037037037',
    '047619047619047619047619047619047619047619',
    '002457002457002457002457002457002457002457',
    '001221001221001221001221001221001221001221',
    '001230012300123001230012300123001230012300123',
    '0013947001394700139470013947001394700139470013947',
    '001001001001001001001001001001001001001001001001001',
    '001406469760900140646976090014064697609',
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

for e in examples:
    sub = repeated(e)
    if sub:
        print("%r: %r" % (e, sub))
    else:
        print("%r does not repeat." % e)

... erzeugt diese Ausgabe:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

Der reguläre Ausdruck (.+?)\1+$ist in drei Teile gegliedert:

  1. (.+?)ist eine übereinstimmende Gruppe, die mindestens ein (aber so wenig wie möglich) Zeichen enthält (weil +?es nicht gierig ist ).

  2. \1+ prüft im ersten Teil auf mindestens eine Wiederholung der übereinstimmenden Gruppe.

  3. $Überprüft das Ende der Zeichenfolge, um sicherzustellen, dass nach den wiederholten Teilzeichenfolgen kein zusätzlicher, sich nicht wiederholender Inhalt vorhanden ist (und re.match()stellt sicher, dass vor den wiederholten Teilzeichenfolgen kein sich nicht wiederholender Text vorhanden ist ).

In Python 3.4 und höher können Sie das ablegen $und re.fullmatch()stattdessen verwenden oder (in jedem Python mindestens bis 2.3) in die andere Richtung gehen und re.search()mit der Regex verwenden ^(.+?)\1+$, die mehr auf den persönlichen Geschmack als auf irgendetwas anderes zurückzuführen ist.

Null Piräus
quelle
6
Ich habe keine Ahnung, warum dieser prägnante Zweiliner nicht die am höchsten bewertete Antwort ist. Die anderen Antworten sind nicht schlecht, aber diese ist weitaus besser. (Es kann den häufig verunglimpften regulären Ausdruck verwenden , aber ich kann dies viel einfacher überprüfen als die anderen viel längeren Antworten, die voller verschachtelter Blöcke, potenzieller Tippfehler, Fehler nacheinander usw. sind.) Ah, schlimmer ist besser Schätze ich.
Paul Draper
9
Ich denke, dafür gibt es zwei Hauptgründe: 1) Einige Programmierer mögen Mathe mehr als Regexe, und 2) da das Variieren der Länge und Art der Eingabezeichenfolgen unterschiedliche Antworten auf die Leistung bringt, die superlangen Randzeichenfolgen (die möglicherweise nicht einmal in den realen Daten enthalten sind) lassen diese Lösung suboptimal erscheinen.
TigerhawkT3
Manchmal stößt man auf große Vorurteile gegenüber regulären Ausdrücken. Ich hatte zwei Manager, die die Verwendung regulärer Ausdrücke verboten haben, weil sie gehört hatten, dass reguläre Ausdrücke das falsche Werkzeug für den Job sind. Außer natürlich baten sie mich dann, eine Regexp-Engine zu implementieren
joojaa
1
@PaulDraper: Ratet mal, was Regex hinter den Kulissen macht? Es analysiert die Zeichenfolge und speichert jedes Element, bis eine mögliche Wiederholung der Wiederholung auftritt. Das ist das gleiche, was OP statet als zu langsam. Nur weil es sich um einen 2-Liner handelt, gibt es keinen Leistungsgewinn.
Dhein
2
@Zaibis, normalerweise stimme ich zu, aber dies ist sowohl die kürzeste als auch die schnellste Lösung ( stackoverflow.com/a/29482936/1212596)....Except for David's, das veröffentlicht wurde, nachdem ich diesen Kommentar abgegeben habe. Ich mag Davids Ansatz eigentlich mehr (klug!).
Paul Draper
90

Sie können die Beobachtung machen, dass die Länge einer Zeichenfolge durch die Länge ihrer wiederholten Sequenz teilbar sein muss, damit sie als Wiederholung betrachtet werden kann. In Anbetracht dessen ist hier eine Lösung, die Teiler der Länge von 1bis n / 2einschließlich generiert , die ursprüngliche Zeichenfolge in Teilzeichenfolgen mit der Länge der Teiler unterteilt und die Gleichheit der Ergebnismenge testet:

from math import sqrt, floor

def divquot(n):
    if n > 1:
        yield 1, n
    swapped = []
    for d in range(2, int(floor(sqrt(n))) + 1):
        q, r = divmod(n, d)
        if r == 0:
            yield d, q
            swapped.append((q, d))
    while swapped:
        yield swapped.pop()

def repeats(s):
    n = len(s)
    for d, q in divquot(n):
        sl = s[0:d]
        if sl * q == s:
            return sl
    return None

BEARBEITEN: In Python 3 hat der /Operator standardmäßig die Float-Division geändert. Um die intUnterteilung von Python 2 zu erhalten, können Sie die verwenden// stattdessen Operator verwenden. Vielen Dank an @ TigerhawkT3, dass Sie mich darauf aufmerksam gemacht haben.

Der //Operator führt sowohl in Python 2 als auch in Python 3 eine Ganzzahldivision durch. Daher habe ich die Antwort aktualisiert, um beide Versionen zu unterstützen. Der Teil, in dem wir testen, ob alle Teilzeichenfolgen gleich sind, ist jetzt eine Kurzschlussoperation mitall und einem Generatorausdruck.

UPDATE: Als Reaktion auf eine Änderung der ursprünglichen Frage wurde der Code jetzt aktualisiert, um den kleinsten sich wiederholenden Teilstring zurückzugeben, falls vorhanden und Nonenicht. @godlygeek hat vorgeschlagen, zu verwendendivmod , die Anzahl der Iterationen auf dem divisorsGenerator zu reduzieren , und der Code wurde entsprechend aktualisiert. Es gibt nun alle positiven Teiler nin aufsteigender Reihenfolge ohne sich nselbst zurück.

Weiteres Update für hohe Leistung: Nach mehreren Tests bin ich zu dem Schluss gekommen, dass das einfache Testen der Zeichenfolgengleichheit die beste Leistung aller Slicing- oder Iteratorlösungen in Python bietet. Daher habe ich ein Blatt aus dem Buch von @ TigerhawkT3 genommen und meine Lösung aktualisiert. Es ist jetzt über 6x so schnell wie zuvor, deutlich schneller als Tigerhawks Lösung, aber langsamer als Davids.

Shashank
quelle
3
Diese Lösung ist erstaunlich. Sie können die Teiler-Methode ändern, um dem Produkt-Verbraucher-Muster zu folgen. Damit es die Ergebnisse liefert, wie sie gefunden werden. Wird eine Schande sein, wenn dies nicht die höchste Antwort ist. Alles andere ist rohe Gewalt.
JustinDanielson
3
@JustinDanielson Gibt ein Generatorobjekt zurück, das aus einem Generatorausdruck erstellt wurde, der ein impliziter Produzent ist :) Die Teiler werden verzögert ausgewertet.
Shashank
1
Ohh. Das wusste ich nicht. Na dann noch besser. : DI verstehen, warum Sie sqrt vermeiden möchten, aber Sie könnten n / 2 als Obergrenze für den Divisor-Bereich verwenden.
JustinDanielson
1
@JustinDanielson Danke für den Vorschlag, die Bereichsobergrenze ist jetzt (n/2)inklusive.
Shashank
1
Sollte n / 2in divisors()sein n // 2?
TigerhawkT3
87

Hier sind einige Benchmarks für die verschiedenen Antworten auf diese Frage. Es gab einige überraschende Ergebnisse, einschließlich einer stark unterschiedlichen Leistung in Abhängigkeit von der getesteten Saite.

Einige Funktionen wurden geändert, um mit Python 3 zu funktionieren (hauptsächlich durch Ersetzen /durch //, um die Ganzzahldivision sicherzustellen). Wenn Sie einen Fehler feststellen, Ihre Funktion hinzufügen oder eine weitere Testzeichenfolge hinzufügen möchten, pingen Sie @ZeroPiraeus im Python-Chatroom .

Zusammenfassend: Es gibt ungefähr einen 50-fachen Unterschied zwischen den Lösungen mit der besten und der schlechtesten Leistung für den großen Satz von Beispieldaten, die hier von OP bereitgestellt werden (über diesen Kommentar). Die Lösung von David Zhang ist der klare Gewinner und übertrifft alle anderen um das Fünffache für das große Beispielset.

Einige der Antworten sind sehr in extrem großen Fällen ohne Übereinstimmung langsam. Ansonsten scheinen die Funktionen je nach Test gleichwertig zu sein oder klare Gewinner zu sein.

Hier sind die Ergebnisse, einschließlich der mit Matplotlib und Seaborn erstellten Diagramme, um die verschiedenen Verteilungen zu zeigen:


Korpus 1 (mitgelieferte Beispiele - kleiner Satz)

mean performance:
 0.0003  david_zhang
 0.0009  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0015  carpetpython
 0.0029  tigerhawk_1
 0.0031  davidism
 0.0035  saksham
 0.0046  shashank
 0.0052  riad
 0.0056  piotr

median performance:
 0.0003  david_zhang
 0.0008  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0014  carpetpython
 0.0027  tigerhawk_1
 0.0031  davidism
 0.0038  saksham
 0.0044  shashank
 0.0054  riad
 0.0058  piotr

Korpus 1 Grafik


Korpus 2 (mitgelieferte Beispiele - großes Set)

mean performance:
 0.0006  david_zhang
 0.0036  tigerhawk_2
 0.0036  antti
 0.0037  zero
 0.0039  carpetpython
 0.0052  shashank
 0.0056  piotr
 0.0066  davidism
 0.0120  tigerhawk_1
 0.0177  riad
 0.0283  saksham

median performance:
 0.0004  david_zhang
 0.0018  zero
 0.0022  tigerhawk_2
 0.0022  antti
 0.0024  carpetpython
 0.0043  davidism
 0.0049  shashank
 0.0055  piotr
 0.0061  tigerhawk_1
 0.0077  riad
 0.0109  saksham

Korpus 1 Grafik


Korpus 3 (Randfälle)

mean performance:
 0.0123  shashank
 0.0375  david_zhang
 0.0376  piotr
 0.0394  carpetpython
 0.0479  antti
 0.0488  tigerhawk_2
 0.2269  tigerhawk_1
 0.2336  davidism
 0.7239  saksham
 3.6265  zero
 6.0111  riad

median performance:
 0.0107  tigerhawk_2
 0.0108  antti
 0.0109  carpetpython
 0.0135  david_zhang
 0.0137  tigerhawk_1
 0.0150  shashank
 0.0229  saksham
 0.0255  piotr
 0.0721  davidism
 0.1080  zero
 1.8539  riad

Korpus 3 Grafik


Die Tests und Rohergebnisse finden Sie hier .

Davidismus
quelle
37

Nicht-Regex-Lösung:

def repeat(string):
    for i in range(1, len(string)//2+1):
        if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
            return string[0:i]

Schnellere Nicht-Regex-Lösung dank @ThatWeirdo (siehe Kommentare):

def repeat(string):
    l = len(string)
    for i in range(1, len(string)//2+1):
        if l%i: continue
        s = string[0:i]
        if s*(l//i) == string:
            return s

Die obige Lösung ist sehr selten um einige Prozent langsamer als das Original, aber normalerweise ein gutes Stück schneller - manchmal sogar viel schneller. Es ist immer noch nicht schneller als das des Davidismus für längere Saiten, und die Regex-Lösung von Zero ist für kurze Saiten überlegen. Es kommt mit Zeichenfolgen von etwa 1000-1500 Zeichen am schnellsten heraus (laut Davidismus-Test auf Github - siehe seine Antwort). Unabhängig davon ist es in allen von mir getesteten Fällen zuverlässig die zweitschnellste (oder bessere). Danke, ThatWeirdo.

Prüfung:

print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

Ergebnisse:

009
2547
abcde
None
None
None
TigerhawkT3
quelle
Ist das nicht eine Brute-Force-Lösung?
JustinDanielson
7
@ JustinDanielson Ja. Aber trotzdem eine Lösung.
Sinkingpoint
3
Ich sehe ungefähr 1e-5 bis 3e-5 Sekunden für kurze Saiten, 3e-5 bis 4e-5 Sekunden für erfolgreiche lange Saiten (1000 Zeichen) und etwas weniger als eine Millisekunde für erfolglose lange Saiten (schlimmster Fall). . Tausend Zeichenfolgen mit 1000 Zeichen würden also ungefähr eine Sekunde dauern. Im Vergleich zur mathematischen Antwort werden Übereinstimmungen zehnmal schneller gefunden, es dauert jedoch dreimal länger, bis sie fehlschlagen.
TigerhawkT3
repeat('aa')kehrt zurückNone
Tom Cornebize
2
len(string[0:i])ist immer gleich i(zumindest in diesem Fall). Das Ersetzen dieser und auch das Speichern len(string)und string[0:i]in Variablen kann die Dinge beschleunigen. Auch IMO ist dies eine großartige Lösung, fantastisch;)
ThatWeirdo
24

Halbieren Sie zunächst die Zeichenfolge, solange es sich um ein "2-teiliges" Duplikat handelt. Dies reduziert den Suchraum bei einer geraden Anzahl von Wiederholungen. Wenn Sie vorwärts arbeiten, um die kleinste sich wiederholende Zeichenfolge zu finden, überprüfen Sie, ob die Aufteilung der vollständigen Zeichenfolge durch eine immer größere Teilzeichenfolge nur zu leeren Werten führt. Es müssen nur Teilstrings length // 2getestet werden, da alles darüber keine Wiederholungen hätte.

def shortest_repeat(orig_value):
    if not orig_value:
        return None

    value = orig_value

    while True:
        len_half = len(value) // 2
        first_half = value[:len_half]

        if first_half != value[len_half:]:
            break

        value = first_half

    len_value = len(value)
    split = value.split

    for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
        if not any(split(value[:i])):
            return value[:i]

    return value if value != orig_value else None

Dies gibt die kürzeste Übereinstimmung zurück oder Keine, wenn keine Übereinstimmung vorliegt.

Davidismus
quelle
16

Das Problem kann O(n)im schlimmsten Fall auch mit der Präfixfunktion gelöst werden.

Beachten Sie, dass es im Allgemeinen langsamer sein kann (UPD: und viel langsamer) als andere Lösungen, die von der Anzahl der Teiler von abhängen n , aber normalerweise früher fehlschlagen. Ich denke, einer der schlechten Fälle für sie wird sein aaa....aab, wo es solche gibtn - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a ‚s

Zunächst müssen Sie die Präfixfunktion berechnen

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    return pi

dann gibt es entweder keine Antwort oder die kürzeste Zeit ist

k = len(s) - prefix_function(s[-1])

und Sie müssen nur überprüfen, ob k != n and n % k == 0 (wenn k != n and n % k == 0dann die Antwort ist s[:k], gibt es keine Antwort

Sie können den Beweis hier überprüfen (auf Russisch, aber der Online-Übersetzer wird wahrscheinlich den Trick machen)

def riad(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    k = n - pi[-1]
    return s[:k] if (n != k and n % k == 0) else None
RiaD
quelle
Ihr prefix_function()Python ist nicht gültig: Sie haben fehlende Doppelpunkte in Ihren whileund if-Anweisungen und &&stattdessen and. Nachdem diese behoben wurden, schlägt dies UnboundLocalError: local variable 'i' referenced before assignmentaufgrund der Leitung fehl for i in range(i, n):.
Zero Piraeus
Danke :-) Wenn Sie eine Funktion zusammenstellen können, die Ihre verwendet prefix_function(), um ähnliche Ergebnisse wie die anderen Antworten zurückzugeben - entweder die kürzeste Teilzeichenfolge oder None-, werde ich sie in einen überarbeiteten Benchmark aufnehmen, den ich zusammenstelle.
Zero Piraeus
@ ZeroPiraeus, es funktioniert eigentlich gut, ich habe es nur falsch genannt
RiaD
16

Diese Version versucht nur die Kandidatensequenzlängen, die Faktoren der Zeichenfolgenlänge sind. und verwendet den *Operator, um eine Zeichenfolge in voller Länge aus der Kandidatensequenz zu erstellen:

def get_shortest_repeat(string):
    length = len(string)
    for i in range(1, length // 2 + 1):
        if length % i:  # skip non-factors early
            continue

        candidate = string[:i]
        if string == candidate * (length // i):
            return candidate

    return None

Vielen Dank an TigerhawkT3, der bemerkt hat, dass dies length // 2ohne + 1den ababFall nicht passen würde .

Antti Haapala
quelle
Diese Lösung ist in der Tat praktisch identisch mit meiner optimierten. Ich sehe, dass Sie ein rangeLimit von haben length//2, genau wie ich - Sie müssen das ändern, length//2+1wenn Sie Zeichenfolgen fangen möchten, die genau verdoppelt sind (z 'aabaab'. B. ).
TigerhawkT3
Und jetzt sind sie identisch! \ o / Ich muss der Optimierung in Zukunft mehr Aufmerksamkeit schenken, aber ich bin froh, dass der Algorithmus selbst solide war.
TigerhawkT3
15

Hier ist eine einfache Lösung ohne reguläre Ausdrücke.

Für Teilketten von saus nullte Index ausgehend von Längen 1 durch len(s), ob die Teilkette , substrdie sich wiederholendes Muster ist. Diese Prüfung kann durchgeführt werden, indem substrmit sich selbst ratioZeiten verkettet werden , so dass die Länge der so gebildeten Zeichenkette gleich der Länge von ist s. Daher ratio=len(s)/len(substr).

Gibt zurück, wenn zuerst ein solcher Teilstring gefunden wird. Dies würde den kleinstmöglichen Teilstring liefern, falls einer existiert.

def check_repeat(s):
    for i in range(1, len(s)):
        substr = s[:i]
        ratio = len(s)/len(substr)
        if substr * ratio == s:
            print 'Repeating on "%s"' % substr
            return
    print 'Non repeating'

>>> check_repeat('254725472547')
Repeating on "2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on "abcde"
Saksham Varma
quelle
Jetzt, da ich mir diese genau anschaue, scheint sie fast identisch mit meiner ursprünglich veröffentlichten Lösung (vor allen Änderungen) zu sein, mit dem einzigen Unterschied, dass die Länge und der Teilstring gespeichert werden. Ich glaube ich hatte einen ziemlich guten Algorithmus. : P
TigerhawkT3
@ TigerhawkT3 Ja in der Tat! :)
Saksham Varma
9

Ich habe mit mehr als acht Lösungen für dieses Problem begonnen. Einige basierten auf Regex (Match, Findall, Split), andere auf dem Schneiden und Testen von Strings, andere auf String-Methoden (Find, Count, Split). Jedes hatte Vorteile in Bezug auf Codeklarheit, Codegröße, Geschwindigkeit und Speicherverbrauch. Ich wollte meine Antwort hier veröffentlichen, als ich bemerkte, dass die Ausführungsgeschwindigkeit als wichtig eingestuft wurde. Deshalb habe ich weitere Tests und Verbesserungen durchgeführt, um dies zu erreichen:

def repeating(s):
    size = len(s)
    incr = size % 2 + 1
    for n in xrange(1, size//2+1, incr):
        if size % n == 0:
            if s[:n] * (size//n) == s:
                return s[:n]

Diese Antwort scheint einigen anderen Antworten hier ähnlich zu sein, hat jedoch einige Geschwindigkeitsoptimierungen, die andere nicht verwendet haben:

  • xrange ist in dieser Anwendung etwas schneller,
  • Wenn eine Eingabezeichenfolge eine ungerade Länge hat, überprüfen Sie keine Teilzeichenfolgen mit gerader Länge.
  • Durch die s[:n]direkte Verwendung vermeiden wir, in jeder Schleife eine Variable zu erstellen.

Es würde mich interessieren, wie sich dies in den Standardtests mit gängiger Hardware verhält. Ich glaube, es wird in den meisten Tests weit hinter David Zhangs exzellentem Algorithmus zurückbleiben, sollte aber ansonsten ziemlich schnell sein.

Ich fand dieses Problem sehr kontraintuitiv. Die Lösungen, von denen ich dachte, sie wären schnell, waren langsam. Die Lösungen, die langsam aussahen, waren schnell! Es scheint, dass Pythons String-Erstellung mit dem Multiplikationsoperator und String-Vergleichen stark optimiert sind.

Logikritter
quelle
Not bad at all :-) Der Benchmark läuft auf Python 3.4 ( zum Teil , weil OP keine Version nicht angibt und das ist , was jeder sollte mit sein, und zum Teil , weil es den neuen nutzt statisticsModul), so musste ich Ihre ändern /s zu //s und ersetzen xrange()mit range()(die verhält sich wie 2.x ist xrange()in 3.x).
Zero Piraeus
Hier sind die Überarbeitungen des Benchmarks, damit Sie meine Änderungen übrigens überprüfen können.
Zero Piraeus
Danke Null. Das war schnell. Die Ergebnisse lagen leicht unter meinen Vorhersagen. Ich vermute, dass die Techniken, die ich in Python 2.7 für die Geschwindigkeit verwendet habe, in Python 3.4 nicht sehr effektiv sind. Na ja - eine lustige und lehrreiche Übung.
Logic Knight
//in 3.x ist die Ganzzahldivision (genau wie das 2.x-Verhalten von /), während 3.x die Gleitdivision /ist (was sicher viel langsamer wäre, selbst wenn es Ihre Lösung nicht durch einen Verwendungsversuch beschädigen würde ein Float als Index). Wie bereits erwähnt, ist 3.x range()dasselbe wie 2.x xrange(); range()In 3.x gibt es kein Äquivalent zu 2.x. Ich denke also nicht, dass dies die Ursache für eine Diskrepanz zwischen dem Benchmark und den von Ihnen vorgenommenen Timings ist. Es ist wahrscheinlich nur so, dass 3.x insgesamt langsamer ist als 2.x (oder vielleicht ist Ihre Maschine schneller als meine).
Zero Piraeus
Wenn ich etwas Zeit habe, werde ich mir die Laufzeitunterschiede zwischen Python 2 und Python 3 genauer ansehen.
Logic Knight
2

Diese Funktion läuft sehr schnell (getestet und ist mehr als dreimal schneller als die schnellste Lösung hier bei Zeichenfolgen mit mehr als 100.000 Zeichen und der Unterschied wird größer, je länger das sich wiederholende Muster ist). Es wird versucht, die Anzahl der Vergleiche zu minimieren, die erforderlich sind, um die Antwort zu erhalten:

def repeats(string):
    n = len(string)
    tried = set([])
    best = None
    nums = [i for i in  xrange(2, int(n**0.5) + 1) if n % i == 0]
    nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
    for s in nums:
        if all(t%s for t in tried):
            print 'Trying repeating string of length:', s
            if string[:s]*(n/s)==string:
                best = s
            else:
                tried.add(s)
    if best:
        return string[:best]

Beachten Sie, dass beispielsweise für eine Zeichenfolge der Länge 8 nur Fragmente der Größe 4 überprüft werden und keine weiteren Tests durchgeführt werden müssen, da das Muster der Länge 1 oder 2 zu einer Wiederholung des Musters der Länge 4 führen würde:

>>> repeats('12345678')
Trying repeating string of length: 4
None

# for this one we need only 2 checks 
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'
Piotr Dabkowski
quelle
Danke :) Ich habe es allerdings nicht sehr optimiert. Ich wollte nur einen anderen Ansatz vorstellen, da sich andere Antworten darauf konzentrieren, das Muster zu finden, und mein Ansatz darauf, zu beweisen, dass es kein Muster gibt :) Daher sollte mein Algorithmus für zufällige Zeichenfolgen viel schneller laufen.
Piotr Dabkowski
0

In David Zhangs Antwort, wenn wir eine Art kreisförmigen Puffer haben, wird dies nicht funktionieren: principal_period('6210045662100456621004566210045662100456621')Aufgrund des Starts 621, wo ich es gerne ausgespuckt hätte:00456621 .

Um seine Lösung zu erweitern, können wir Folgendes verwenden:

def principal_period(s):
    for j in range(int(len(s)/2)):
        idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
        if idx != -1:
            # Make sure that the first substring is part of pattern
            if s[:j] == s[j:][:idx][-j:]:
                break

    return None if idx == -1 else s[j:][:idx]

principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'
Sachinruk
quelle
-1

Hier ist der Code in Python, der die Wiederholung der Unterzeichenfolge in der vom Benutzer angegebenen Hauptzeichenfolge überprüft .

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''):
    print "Invalid string"
    exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
    strarr=strarr+charlist[i]
    splitlist=mainstring.split(strarr)
    count = 0
    for j in splitlist:
        if j =='':
            count+=1
    if count == len(splitlist):
        break
if count == len(splitlist):
    if count == 2:
        print "No repeating Sub-String found in string %r"%(mainstring)

    else:
        print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
    print "No repeating Sub-String found in string %r"%(mainstring)

Eingabe :

0045662100456621004566210045662100456621

Ausgabe :

Länge Ihrer Saite: 40

Die Unterzeichenfolge '00456621' wird in der Zeichenfolge '0045662100456621004566210045662100456621' wiederholt.

Eingabe :

004608294930875576036866359447

Ausgabe :

Länge Ihrer Saite: 30

In der Zeichenfolge '004608294930875576036866359447' wurde kein sich wiederholender Sub-String gefunden.

Srivishnu
quelle