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

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?

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.

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.

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.

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

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

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

Testy i surowe wyniki są dostępne tutaj .

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

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.

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

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.

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"

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.

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'

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'

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”