Jak mogę sprawdzić, czy ciąg znaków powtarza się w Pythonie?

352

Szukam sposobu, aby sprawdzić, czy dany ciąg powtarza się dla całego ciągu, czy nie.

Przykłady:

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

są ciągami, które się powtarzają, i

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

to przykłady takich, które tego nie robią.

Powtarzane sekcje ciągów, które otrzymałem, mogą być dość długie, a same ciągi mogą mieć co najmniej 500 znaków, więc zapętlanie każdego znaku, próbując zbudować wzór, a następnie sprawdzanie wzoru względem reszty ciągu wydaje się okropnie wolne. Pomnóż to przez potencjalnie setki ciągów, a nie widzę żadnego intuicyjnego rozwiązania.

Przeszukałem trochę wyrażeń regularnych i wydają się one przydatne, gdy wiesz, czego szukasz, lub przynajmniej długość szukanego wzoru. Niestety nie znam żadnego z nich.

Jak mogę stwierdzić, czy ciąg się powtarza, a jeśli tak, to jaka jest najkrótsza powtarzalna podsekwencja?

Jan
źródło
15
zapętlanie każdej postaci próbującej zbudować wzór, a następnie sprawdzanie wzorca względem reszty łańcucha wydaje się okropnie wolne - ale czy tak?
Tim
2
@AvinashRaj To tylko pasująca część łańcucha, a nie cała rzecz.
Jana
11
@AvinashRaj OP pyta o wszystkie możliwe rozwiązania. Pytanie, do którego prowadzi link, akceptuje tylko rozwiązanie wyrażenia regularnego . Pamiętaj, że regex może rozwiązać problem, ale w znacznie dłuższym czasie niż to konieczne. Na przykład optymalne rozwiązanie (tj. Czas liniowy) użyłoby drzewa sufiksów tekstu. Musisz tylko znaleźć najdłuższy powtarzający się podciąg i wykonać kilka kontroli długości.
Bakuriu,
2
@ TigerhawkT3 Prawdziwy zestaw danych jest o wiele za duży i nieporęczny, ale przykłady w pytaniu są jego częścią, a jeśli chcesz, oto kilka innych .
John

Odpowiedzi:

570

Oto zwięzłe rozwiązanie, które pozwala uniknąć wyrażeń regularnych i wolnych pętli w Pythonie:

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

Zobacz odpowiedź Wiki Wiki rozpoczętą przez @davidism, aby uzyskać wyniki testów porównawczych. W podsumowaniu,

Rozwiązanie Davida Zhanga jest wyraźnym zwycięzcą, wyprzedzając wszystkich innych o co najmniej 5 razy w przypadku dużego zestawu przykładów.

(Słowa tej odpowiedzi, nie moje).

Jest to oparte na spostrzeżeniu, że łańcuch jest okresowy wtedy i tylko wtedy, gdy jest równy nietrywialnej rotacji samego siebie. Wyrazy uznania dla @AleksiTorhamo za uświadomienie sobie, że możemy odzyskać okres główny z indeksu pierwszego wystąpienia sin (s+s)[1:-1], oraz za poinformowanie mnie o opcjonalności starti endargumentach Pythona string.find.

David Zhang
źródło
19
Możesz to rozszerzyć, aby znaleźć najkrótsze powtarzające się podsekwencje, używając .find()lub .index()zamiast in, np. (s+s).find(s, 1, -1).
Aleksi Torhamo
11
Myślę też, że (s+s).find(s, 1, -1)będzie (bardzo nieznacznie) szybszy niż (s+s)[1:-1].find(s), przynajmniej w przypadku większych ciągów, ponieważ przecinanie oznacza, że ​​musisz utworzyć kolejną kopię (prawie) całego ciągu.
Aleksi Torhamo
13
To tak, jakby wziąć falę grzechu lub cos z funkcji okresowej i przesunąć ją w prawo. Ponieważ fale są w pełni okresowe, fale ostatecznie będą idealnie pasować ... Równania matematyczne z tym rozwiązaniem są po prostu fenomenalne. :) Chciałbym móc dać + ∞ głosów pozytywnych.
Shashank
6
Ostatnia aktualizacja Guido do PEP 8 jest tutaj istotna: „Zachowaj spójność instrukcji return. Albo wszystkie instrukcje return w funkcji powinny zwracać wyrażenie, albo żadna z nich nie powinna. Jeśli jakakolwiek instrukcja return zwraca wyrażenie, wszelkie instrukcje return, w których nie ma wartości zwrócone powinno jawnie podawać to jako return None, a na końcu funkcji powinna znajdować się wyraźna instrukcja return (jeśli jest osiągalna). ”
Zero Pireus
8
@WayneConrad Weź ciąg, powiedzmy, oderwij "abcd"postać z prawej strony i przyklej ją z powrotem w lewo, aby uzyskać "dabc". Ta procedura nazywa się obracaniem łańcucha w prawo o 1 znak . Powtarzaj nczasy, aby obracać ciąg znaków w prawo o nznaki. Teraz zauważ, że jeśli mamy ciąg kznaków, obrót w prawo o dowolną wielokrotność kpozostawia ciąg bez zmian. Nietrywialna obrót ciąg jest jednym których liczba znaków nie jest wielokrotnością długości struny.
David Zhang
181

Oto rozwiązanie wykorzystujące wyrażenia regularne.

import re

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

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

Iterowanie po przykładach w pytaniu:

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)

... tworzy ten wynik:

'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.

Wyrażenie regularne (.+?)\1+$dzieli się na trzy części:

  1. (.+?)to dopasowana grupa zawierająca co najmniej jedną (ale jak najmniej) jakąkolwiek postać (ponieważ +?jest nie chciwa ).

  2. \1+ sprawdza co najmniej jedno powtórzenie pasującej grupy w pierwszej części.

  3. $sprawdza koniec łańcucha, aby upewnić się, że po powtórzonych podciągach nie ma dodatkowej, niepowtarzalnej treści (i użycie re.match()zapewnia, że przed powtarzającymi się podciągami nie będzie żadnego powtarzającego się tekstu ).

W Pythonie 3.4 i nowszych możesz zamiast tego $użyć i re.fullmatch()lub (w każdym Pythonie co najmniej aż do wersji 2.3) przejść w drugą stronę i użyć re.search()wyrażenia regularnego ^(.+?)\1+$, z których wszystkie są bardziej zależne od osobistego gustu niż cokolwiek innego.

Zero Pireus
źródło
6
Nie mam pojęcia, dlaczego ta zwięzła dwuwarstwowa nie jest najlepiej głosowaną odpowiedzią. Pozostałe odpowiedzi nie są złe, ale ta jest o wiele lepsza. (Może używać często oczernianego wyrażenia regularnego , ale mogę sprawdzić to znacznie łatwiej niż inne znacznie dłuższe odpowiedzi, które są pełne zagnieżdżonych bloków, potencjalnych literówek, błędów pojedynczych itd.) Cóż, gorsze jest lepsze Przypuszczam.
Paul Draper,
9
Myślę, że istnieją dwa główne powody: 1) niektórzy programiści lubią matematykę bardziej niż wyrazy regularne, oraz 2) ponieważ zmienianie długości i charakteru ciągów wejściowych powoduje, że różne odpowiedzi podążają za wydajnością, ciągi super-długich krawędzi (które mogą nawet nie pojawić się w rzeczywistych danych) sprawiają, że to rozwiązanie wydaje się nieoptymalne.
TigerhawkT3
czasami napotykasz wielkie uprzedzenia do wyrażeń regularnych. Miałem 2 menedżerów, którzy zabronili używania wyrażeń regularnych, ponieważ słyszeli, że wyrażenia regularne są niewłaściwym narzędziem do pracy. Z wyjątkiem offcourse, następnie poprosili mnie o wdrożenie silnika regexp
joojaa
1
@PaulDraper: Zgadnij, co regex robi za sceną? parsuje ciąg i przechowuje każdy element, aż do wystąpienia możliwego dopasowania ponownego zapisu. To to samo, co statystyki OP za zbyt wolne. tylko dlatego, że jest to 2 liniowiec, nie ma żadnej wygranej wydajności.
dhein
2
@Zaibis, zazwyczaj się zgadzam, ale jest to zarówno najkrótsze, jak i najszybsze rozwiązanie ( stackoverflow.com/a/29482936/1212596). Z wyjątkiem Davida, który został opublikowany po tym, jak skomentowałem. Właściwie podoba mi się podejście Davida (sprytne!).
Paul Draper,
90

Możesz dokonać obserwacji, że aby łańcuch mógł być uważany za powtarzalny, jego długość musi być podzielna przez długość jego powtarzanej sekwencji. Biorąc to pod uwagę, oto rozwiązanie, które generuje dzielniki długości od 1do n / 2włącznie, dzieli oryginalny ciąg na podciągi o długości dzielników i testuje równość zestawu wyników:

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

EDYCJA: W Pythonie 3 /operator zmienił się domyślnie na podział zmiennoprzecinkowy. Aby uzyskać intpodział z Python 2, możesz //zamiast tego użyć operatora. Dziękuję @ TigerhawkT3 za zwrócenie mojej uwagi na to.

Że //operator wykonuje całkowite podziału zarówno Python 2 i Python 3, więc już zaktualizowane odpowiedź na poparcie obu wersji. Część, w której testujemy, czy wszystkie podciągi są równe, jest teraz operacją zwarcia alli wyrażeniem generatora.

AKTUALIZACJA: W odpowiedzi na zmianę w pierwotnym pytaniu kod został teraz zaktualizowany, aby zwracał najmniejsze powtarzające się podciągi, jeśli istnieje, a Nonejeśli nie. @godlygeek zasugerował użycie w divmodcelu zmniejszenia liczby iteracji w divisorsgeneratorze, a także kod został zaktualizowany, aby pasował do tego. Teraz zwraca wszystkie pozytywne dzielniki zn w porządku rosnącym, z wyłączeniem nsiebie.

Dalsza aktualizacja w celu uzyskania wysokiej wydajności: po wielu testach doszedłem do wniosku, że po prostu testowanie pod kątem równości łańcuchów ma najlepszą wydajność z dowolnego rozwiązania krojenia lub iteratora w Pythonie. Dlatego wyciągnąłem liść z książki @ TigerhawkT3 i zaktualizowałem moje rozwiązanie. Jest teraz ponad 6 razy szybszy niż wcześniej, zauważalnie szybszy niż rozwiązanie Tigerhawk, ale wolniejszy niż David.

Shashank
źródło
3
To rozwiązanie jest niesamowite. Możesz zmienić metodę dzielników, aby była zgodna z wzorcem produkcji-konsumenta. Tak, aby przyniosło wyniki w takiej postaci, w jakiej zostały znalezione. Będzie szkoda, jeśli nie będzie to najwyższa odpowiedź. Cała reszta to brutalna siła.
JustinDanielson,
3
@JustinDanielson Zwraca obiekt generatora utworzony z wyrażenia generatora, który jest domyślnym producentem :) Będzie leniwie oceniał dzielniki.
Shashank,
1
Och Nie wiedziałem tego Cóż, nawet lepiej. : DI rozumiem, dlaczego chcesz unikać sqrt, ale możesz użyć n / 2 jako górnej granicy zakresu dzielnika.
JustinDanielson,
1
@JustinDanielson Dzięki za sugestię, górna granica zakresu jest teraz włączona (n/2).
Shashank,
1
Należy n / 2w divisors()być n // 2?
TigerhawkT3
87

Oto kilka punktów odniesienia dla różnych odpowiedzi na to pytanie. Było kilka zaskakujących wyników, w tym bardzo różna wydajność w zależności od testowanego ciągu.

Niektóre funkcje modyfikowano do pracy z Pythonie 3 (głównie przez zastąpienie /w //celu zapewnienia podziału całkowita). Jeśli widzisz coś nie tak, chcesz dodać swoją funkcję lub chcesz dodać kolejny ciąg testowy, ping @ ZeroPiraeus w czacie Python .

Podsumowując: istnieje około 50-krotna różnica między najlepiej i najgorzej działającymi rozwiązaniami dla dużego zestawu przykładowych danych dostarczonych tutaj przez OP (poprzez ten komentarz). Rozwiązanie Davida Zhanga jest wyraźnym zwycięzcą, przewyższając wszystkich innych o około 5 razy w przypadku dużego zestawu przykładów.

Kilka odpowiedzi jest bardzo wolnych w bardzo dużych przypadkach „bez dopasowania”. W przeciwnym razie funkcje wydają się być jednakowo dopasowane lub jasne zwycięzcy w zależności od testu.

Oto wyniki, w tym wykresy wykonane przy użyciu matplotlib i seaborn, aby pokazać różne rozkłady:


Corpus 1 (dostarczone przykłady - mały zestaw)

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

Wykres korpusu 1


Corpus 2 (dostarczone przykłady - duży zestaw)

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

Wykres korpusu 1


Corpus 3 (przypadki na krawędziach)

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

Wykres Corpus 3


Testy i surowe wyniki są dostępne tutaj .

dawidyzm
źródło
37

Rozwiązanie inne niż wyrażenia regularne:

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]

Szybsze rozwiązanie bez wyrażenia regularnego, dzięki @ThatWeirdo (patrz komentarze):

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

Powyższe rozwiązanie jest bardzo rzadko wolniejsze od oryginału o kilka procent, ale zwykle jest nieco szybsze - czasem o wiele szybsze. Nadal nie jest szybszy niż dawidyzm dla dłuższych łańcuchów, a rozwiązanie wyrażenia regularnego zera jest lepsze dla krótkich łańcuchów. Najszybszy (zgodnie z testem dawidyzmu na githubie - patrz jego odpowiedź) z ciągami około 1000-1500 znaków. Niezależnie od tego, jest niezawodnie drugi najszybszy (lub lepszy) we wszystkich testowanych przeze mnie przypadkach. Dzięki, ThatWeirdo.

Test:

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

Wyniki:

009
2547
abcde
None
None
None
TigerhawkT3
źródło
Czy to nie jest rozwiązanie brutalnej siły?
JustinDanielson,
7
@JustinDanielson Tak. Niemniej jednak rozwiązanie.
Sinkingpoint
3
Widzę około 1e-5 do 3e-5 sekund dla krótkich ciągów, 3e-5 do 4e-5 sekund dla udanych długich (1000 znaków) ciągów i trochę poniżej milisekundy dla nieudanych długich ciągów (najgorszy przypadek) . Tak więc tysiąc ciągów znaków o długości 1000 znaków zajmie około sekundy. W porównaniu z odpowiedzią matematyczną wyniki wyszukiwania są 10-krotnie szybsze, ale 3-krotnie dłużej trwa niepowodzenie.
TigerhawkT3
repeat('aa')powracaNone
Tom Cornebize,
2
len(string[0:i])jest zawsze równa i(przynajmniej w tym przypadku). Zastąpienie ich, a także zapisanie len(string)i string[0:i]zmienne mogą przyspieszyć. Również IMO to świetne rozwiązanie, niesamowite;)
ThatWeirdo,
24

Najpierw podziel ciąg o połowę, o ile jest to duplikat „2 części”. Zmniejsza to przestrzeń wyszukiwania, jeśli jest parzysta liczba powtórzeń. Następnie, pracując naprzód, aby znaleźć najmniejszy powtarzający się ciąg, sprawdź, czy podzielenie pełnego ciągu na coraz większe podciąg powoduje tylko puste wartości. length // 2Konieczne jest przetestowanie tylko podłańcuchów , które nie będą się powtarzać.

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

Zwraca najkrótsze dopasowanie lub Brak, jeśli nie ma żadnego dopasowania.

dawidyzm
źródło
16

Problem można również rozwiązać O(n)w najgorszym przypadku dzięki funkcji prefiksu.

Zauważ, że może być wolniejszy w ogólnym przypadku (UPD: i jest znacznie wolniejszy) niż inne rozwiązania, które zależą od liczby dzielników n, ale zwykle nie udaje się wcześniej, myślę, że jednym ze złych przypadków będzie aaa....aab, jeśli sąn - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a „s

Przede wszystkim musisz obliczyć funkcję prefiksu

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

wtedy albo nie ma odpowiedzi, albo jest najkrótszy okres

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

i musisz tylko sprawdzić, czy k != n and n % k == 0(jeśli tak, k != n and n % k == 0to odpowiedź brzmis[:k] , inaczej nie ma odpowiedzi

Możesz sprawdzić dowód tutaj (po rosyjsku, ale tłumacz online prawdopodobnie załatwi sprawę)

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
źródło
Twój prefix_function()niepoprawny Python: brakuje dwukropków na twoim whilei ifwyciągu, a &&zamiast and. Po ich naprawieniu nie udaje się z UnboundLocalError: local variable 'i' referenced before assignmentpowodu linii for i in range(i, n):.
Zero Pireus
Dzięki :-) Jeśli możesz połączyć funkcję, która używa twojej, prefix_function()aby zwrócić podobne wyniki do innych odpowiedzi - albo najkrótszy podciąg, albo None- uwzględnię go w poprawionym teście porównawczym, który zestawiam.
Zero Pireus
@ ZeroPiraeus, Właściwie to działa dobrze, właśnie nazwałem to źle
RiaD
16

Ta wersja próbuje tylko tych długości sekwencji kandydujących, które są czynnikami długości łańcucha; i używa *operatora do zbudowania ciągu o pełnej długości z sekwencji kandydującej:

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

Dzięki TigerhawkT3 za zauważenie, że length // 2bez + 1nie pasowałoby do ababprzypadku.

Antti Haapala
źródło
To rozwiązanie jest faktycznie identyczne z moim zoptymalizowanym. Widzę, że masz rangelimit length//2, tak jak ja - musisz to zmienić, length//2+1jeśli chcesz złapać dokładnie podwojone łańcuchy (np 'aabaab'.).
TigerhawkT3
A teraz są identyczne! \ o / Muszę w przyszłości zwracać większą uwagę na optymalizację, ale cieszę się, że sam algorytm był dobry.
TigerhawkT3
15

Oto proste rozwiązanie, bez wyrażeń regularnych.

W przypadku podciągów szaczynających się od indeksu zerowego, o długości od 1 do len(s), sprawdź, czy podciąg substrjest powtórzeniem wzoru. To sprawdzenie można wykonać, łącząc się substrze sobąratio czasów, tak aby długość utworzonego w ten sposób łańcucha była równa długości s. W związku z tymratio=len(s)/len(substr) .

Wróć po znalezieniu pierwszego takiego podciągu. Zapewniłoby to możliwie najmniejszy podciąg, jeśli taki istnieje.

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
źródło
Teraz, gdy patrzę na to uważnie, wydaje się on prawie identyczny z moim pierwotnie opublikowanym (przed wszelkimi edycjami) rozwiązaniem, z jedynymi różnicami polegającymi na zapisaniu długości i podłańcucha. Chyba miałem całkiem niezły algorytm. : P
TigerhawkT3 10.04.15
@ TigerhawkT3 Tak, rzeczywiście! :)
Saksham Varma
9

Zacząłem od ponad ośmiu rozwiązań tego problemu. Niektóre opierały się na wyrażeniach regularnych (dopasowywanie, znajdowanie, dzielenie), niektóre na cięciach i testowaniu ciągów, a niektóre na metodach ciągowych (znajdź, policz, podziel). Każdy z nich miał zalety w zakresie przejrzystości kodu, rozmiaru kodu, szybkości i zużycia pamięci. Zamierzałem zamieścić tutaj swoją odpowiedź, gdy zauważyłem, że szybkość wykonania została sklasyfikowana jako ważna, dlatego wykonałem więcej testów i ulepszeń, aby to osiągnąć:

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]

Ta odpowiedź wydaje się podobna do kilku innych odpowiedzi tutaj, ale ma kilka optymalizacji prędkości, których inni nie używali:

  • xrange jest nieco szybszy w tej aplikacji,
  • jeśli łańcuch wejściowy ma nieparzystą długość, nie sprawdzaj podciągów o równej długości,
  • Używając s[:n]bezpośrednio, unikamy tworzenia zmiennej w każdej pętli.

Byłbym zainteresowany, aby zobaczyć, jak to działa w standardowych testach na zwykłym sprzęcie. Sądzę, że w większości testów nie będzie to doskonały algorytm Davida Zhanga, ale w przeciwnym razie powinien być dość szybki.

Uważam, że ten problem jest bardzo sprzeczny z intuicją. Rozwiązania, które moim zdaniem będą szybkie, były powolne. Rozwiązania, które wyglądały powoli, były szybkie! Wygląda na to, że tworzenie napisów w Pythonie za pomocą operatora mnożenia i porównywania napisów jest wysoce zoptymalizowane.

Logic Knight
źródło
Wcale nieźle :-) Test porównawczy działa na Pythonie 3.4 (częściowo dlatego, że OP nie określa wersji i tego powinien używać każdy , a częściowo dlatego, że używa nowego statisticsmodułu), więc musiałem zmienić twoje /s na //s i wymienić xrange()z range()(który zachowuje się jak 2.x użytkownika xrange()w wersji 3.x).
Zero Pireus
Oto zmiany w teście porównawczym, więc przy okazji możesz przejrzeć moje zmiany.
Zero Pireus
Dzięki zero. To było szybkie. Wyniki nieznacznie obniżyły moje przewidywania. Podejrzewam, że techniki, których użyłem do prędkości w Pythonie 2.7, nie są zbyt skuteczne w Pythonie 3.4. No cóż - zabawne i edukacyjne ćwiczenie.
Logic Knight
//w 3.x jest dzieleniem całkowitym (podobnie jak zachowanie 2.x /), podczas gdy 3.x /to dzielenie zmiennoprzecinkowe (co na pewno byłoby znacznie wolniejsze, nawet gdyby nie złamało twojego rozwiązania powodując próbę użycia liczba zmiennoprzecinkowa jako indeks). Jak wspomniano, 3.x range()jest tym samym, co 2.x xrange(); nie ma odpowiednika 2.x range()w 3.x. Więc nie sądzę, że jest to przyczyną jakiejkolwiek rozbieżności między testem porównawczym a ustalonymi czasami. Prawdopodobnie po prostu 3.x jest wolniejszy niż 2.x (a może twoja maszyna jest szybsza niż moja).
Zero Pireus
Kiedy będę miał trochę czasu, przyjrzę się bliżej różnicom w czasie wykonywania między Pythonem 2 i Pythonem 3.
Logic Knight
2

Ta funkcja działa bardzo szybko (przetestowana i jest ponad 3 razy szybsza niż najszybsze rozwiązanie tutaj na ciągach o ponad 100 000 znaków, a różnica staje się większa, im dłuższy jest powtarzalny wzór). Stara się zminimalizować liczbę porównań potrzebnych do uzyskania odpowiedzi:

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]

Zauważ, że na przykład dla ciągu o długości 8 sprawdza tylko fragment o rozmiarze 4 i nie musi dalej testować, ponieważ wzorzec o długości 1 lub 2 spowodowałby powtórzenie wzorca o długości 4:

>>> 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
źródło
Dziękuję :) Nie zoptymalizowałem tego jednak zbytnio. Chciałem tylko przedstawić inne podejście, ponieważ inne odpowiedzi koncentrują się na znalezieniu wzorca, a moje podejście skupia się na udowodnieniu, że nie ma wzorca :) Dlatego dla losowych ciągów mój algorytm powinien działać znacznie szybciej.
Piotr Dąkowski
0

W odpowiedzi Davida Zhanga, jeśli mamy jakiś bufor okrągły, to nie zadziała: principal_period('6210045662100456621004566210045662100456621')ze względu na początek 621, w którym chciałbym, żeby wypluł:00456621 .

Rozszerzając jego rozwiązanie, możemy użyć:

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
źródło
-1

Oto kod w pythonie, który sprawdza powtarzalność podciągu w głównym ciągu podanym przez użytkownika .

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)

Wejście :

0045662100456621004566210045662100456621

Wyjście :

Długość sznurka: 40

Ciąg podrzędny „00456621” powtarza się w ciągu „0045662100456621004566210045662100456621”

Wejście :

004608294930875576036866359447

Wyjście :

Długość sznurka: 30

Nie znaleziono powtarzającego się podciągu w ciągu „004608294930875576036866359447”

Srivishnu
źródło