Как я могу сказать, если строка повторяется в Python?

вот решение с использованием регулярных выражений.

import re

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

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

повторяя примеры в вопросе:

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)

... производит этот вывод:

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

регулярное выражение (.+?)+$ разделен на три части:

1. (.+?) соответствующая группа, содержащая по крайней мере один (но как можно меньше) любого персонажа (потому что +? is не жадный).

2. + проверяет наличие хотя бы одного повторения соответствующей группы в первой части.

3. $ проверяет конец строки, чтобы убедиться, что нет дополнительного, неповторяющегося содержимого после повторяющихся подстрок (и с помощью re.match() гарантирует, что нет неповторяющегося текста до повторяющиеся подстроки).

в Python 3.4 и позже, вы могли бы бросить $ и использовать re.fullmatch() вместо этого или (в любом Python, по крайней мере, до 2.3) идите в другую сторону и используйте re.search() с регулярным выражением ^(.+?)+$, все из которых больше по личному вкусу, чем что-либо еще.

вы можете сделать замечание, что для того, чтобы строка считалась повторяющейся, ее длина должна быть кратна длине ее повторной последовательности. Учитывая это, вот решение, которое генерирует делители длины от 1 to n / 2 включительно, делит исходную строку на подстроки с длиной делителей и проверяет равенство результирующего набора:

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

EDIT: в Python 3,/ оператор изменился, чтобы сделать поплавок деление по умолчанию. Чтобы получить int отдела от Python 2, Вы можете использовать // оператор вместо этого. Спасибо @TigerhawkT3 за доведение этого до моего сведения.

The // оператор выполняет целочисленное деление как в Python 2, так и в Python 3, поэтому я обновил ответ для поддержки обеих версий. Часть, где мы проверяем, чтобы увидеть, если все подстроки равны, теперь является операцией короткого замыкания с использованием all и генератор выражение.

обновление: в ответ на изменение исходного вопроса, код теперь был обновлен, чтобы вернуть наименьшую повторяющуюся подстроку, если она существует и None если это не так. @godlygeek предложил использовать divmod чтобы уменьшить количество итераций на divisors генератор, и код был обновлен, чтобы соответствовать, что также. Теперь он возвращает все положительные делители n в порядке возрастания, исключая n себя.

дальнейшее обновление для высокой производительности: после нескольких тестов я пришел к выводу, что простое тестирование на равенство строк имеет лучшую производительность из любого решения для нарезки или итератора в Python. Таким образом, я взял лист из книги @TigerhawkT3 и обновил свое решение. Теперь он в 6 раз быстрее, чем раньше, заметно быстрее, чем решение Tigerhawk, но медленнее, чем у Дэвида.

вот некоторые ориентиры для различных ответов на этот вопрос. Были некоторые удивительные результаты, в том числе дико различная производительность в зависимости от тестируемой строки.

некоторые функции были изменены для работы с Python 3 (в основном путем замены / С // для обеспечения целочисленного деления). Если вы видите что-то не так, хотите добавить свою функцию или хотите добавить еще одну тестовую строку, ping @ZeroPiraeus в Python чат.

вкратце: существует примерно 50-кратная разница между лучшими и худшими решениями для большого набора примеров данных, предоставленных OP здесь (через этой комментарий). решение Дэвида Чжана является явным победителем, опережая всех остальных примерно в 5 раз для большого набора примеров.

несколько ответов очень медленно в очень больших случаях "нет совпадения". В противном случае, функции кажется быть равен или явными победителями в зависимости от теста.

вот результаты, в том числе графики, сделанные с использованием matplotlib и seaborn, чтобы показать различные распределения:

---

корпус 1 (прилагаемые примеры - малый набор)

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

---

корпус 2 (прилагаемые примеры-большие комплект)

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

---

корпус 3 (крайние случаи)

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

---

тесты и необработанные результаты доступны здесь.

нерегулярное решение:

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]

более быстрое решение без регулярных выражений, благодаря @ThatWeirdo (см. комментарии):

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

выше решение очень редко медленнее, чем оригинал на несколько процентов, но это, как правило, немного быстрее - иногда намного быстрее. Это все еще не быстрее, чем davidism для более длинных строк, а решение регулярных выражений zero превосходит короткие строки. Он выходит на самый быстрый (согласно тесту давидизма на github-см. Его ответ) с строк около 1000-1500 символов. Несмотря на это, он надежно второй по скорости (или лучше) во всех случаях, которые я тестировал. Спасибо, Этот Чудак.

во-первых, разделите строку пополам, пока это дубликат "2 части". Это сокращает пространство поиска, если есть четное число повторов. Затем, работая вперед, чтобы найти наименьшую повторяющуюся строку, проверьте, не приводит ли разделение полной строки на все большую подстроку только к пустым значениям. Только подстроки до length // 2 нужно проверить, так как все, что над этим не будет иметь повторений.

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

это возвращает самое короткое совпадение или нет, если нет спичка.

проблема может быть решена в O(n) в худшем случае с функцией префикс.

обратите внимание, что он может быть медленнее в общем случае (UPD: и намного медленнее), чем другие решения, которые зависят от количества делителей n, но обычно найти не удается раньше, я думаю, что один из плохих случаев для них будет aaa....aab, где находятся n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1a ' s

прежде всего вам нужно вычислить префикс функции

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

тогда либо нет ответа, либо самый короткий период

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

и вы просто должны проверить, если k != n and n % k == 0 (если k != n and n % k == 0 тогда ответ s[:k], иначе нет ответа

вы можете проверить доказательство здесь (на русском языке, но онлайн-переводчик, вероятно, сделать трюк)

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

эта версия пробует только те длины последовательности кандидатов, которые являются факторами длины строки; и использует * оператор для построения полнометражной строки из последовательности кандидатов:

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

спасибо TigerhawkT3 за то, что заметил это length // 2 без + 1 не соответствует abab случае.

вот прямое решение, без регулярных выражений.

для подстроки s начиная с нулевого индекса, длин от 1 до len(s), проверьте, если эта подстрока,substr - это повторяющийся узор. Эта проверка может быть выполнена путем объединения substr С ratio раз, так что длина сформированной таким образом строки равна длине s. Отсюда ratio=len(s)/len(substr).

возврат при первом обнаружении такой подстроки. Это даст наименьшая возможная подстрока, если она существует.

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"

Я начал с более чем восьми решений этой проблемы. Некоторые из них были основаны на регулярных выражениях (match, findall, split), некоторые из строк нарезки и тестирования, а некоторые со строковыми методами (find, count, split). У каждого из них были преимущества в ясности кода, размере кода, скорости и потреблении памяти. Я собирался опубликовать свой ответ здесь, когда заметил, что скорость выполнения была оценена как важная, поэтому я сделал больше тестов и улучшений, чтобы прийти к этому:

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]

этот ответ кажется похожим на несколько другие ответы здесь, но у него есть несколько оптимизаций скорости, которые другие не использовали:

• xrange немного быстрее в этом приложении
• если входная строка имеет нечетную длину, не проверяйте подстроки четной длины,
• С помощью s[:n] напрямую, мы избегаем создания переменной в каждом цикле.

мне было бы интересно посмотреть, как это работает в стандартных тестах с общим оборудованием. Я считаю, что это будет хорошо не хватает Дэвида Отличный алгоритм Чжана в большинстве тестов, но должен быть довольно быстрым в противном случае.

я обнаружил, что эта проблема очень противоречива. Решения, которые я думал, будут быстрыми, были медленными. Решения, которые выглядели медленными, были быстрыми! Похоже, что создание строки Python с помощью оператора multiply и сравнения строк сильно оптимизированы.

эта функция работает очень быстро (проверено, и это более чем в 3 раза быстрее, чем самое быстрое решение здесь на строках с более чем 100k символов и разница становится больше, чем дольше повторяющийся шаблон). Он пытается свести к минимуму количество сравнений, необходимых для получения ответа:

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]

обратите внимание, что, например, для строки длины 8 он проверяет только фрагмент размера 4, и ему не нужно проверять дальше, потому что шаблон длины 1 или 2 приведет к повторению шаблона длина 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'

в ответе Дэвида Чжана, если у нас есть какой-то круговой буфер, это не сработает: principal_period('6210045662100456621004566210045662100456621') из-за старта 621, где бы мне хотелось его выплюнуть:00456621.

расширяет свое решение, мы можем использовать следующее:

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'

вот код в python, который проверяет повторение подстроки в главной строке, заданной пользователем.

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)

вход:

0045662100456621004566210045662100456621

выход:

длина строки : 40

подстрока '00456621' повторяется в строке '0045662100456621004566210045662100456621'

вход:

004608294930875576036866359447

выход:

длина строки : 30

нет повторяющихся подстрок, найденных в строке '004608294930875576036866359447'