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

352

Я ищу способ проверить, повторяется ли данная строка для всей строки или нет.

Примеры:

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

являются строками, которые повторяются, и

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

примеры тех, которые этого не делают.

Повторяющиеся фрагменты строк, которые мне даны, могут быть довольно длинными, а сами строки могут содержать 500 или более символов, поэтому циклически проходя по каждому символу, пытаясь построить шаблон, затем проверяя шаблон по сравнению с остальной строкой, кажется ужасно медленным. Умножьте это на потенциально сотни строк, и я не вижу никакого интуитивного решения.

Я немного изучил регулярные выражения, и они кажутся полезными, когда вы знаете, что ищете, или, по крайней мере, длину шаблона, который ищете. К сожалению, я не знаю ни того, ни другого.

Как я могу определить, является ли строка повторяющейся, и если это так, какова самая короткая повторяющаяся подпоследовательность?

Джон
источник
15
цикл по каждому символу, пытающийся построить шаблон, затем проверка шаблона против остальной части строки кажется ужасно медленной - но так ли это?
Тим
2
@AvinashRaj Это только соответствующая часть строки, а не полная.
Джон
11
@AvinashRaj ОП спрашивает обо всех возможных решениях. Вопрос, на который вы ссылаетесь, принимает только решение регулярных выражений . Обратите внимание, что регулярное выражение может решить проблему, но за гораздо большее время, чем необходимо. Например, оптимальное решение (т.е. линейное время) будет использовать дерево суффиксов текста. Вам просто нужно найти самую длинную повторяемую подстроку и сделать несколько проверок длины.
Бакуриу
2
@ TigerhawkT3 Реальный набор данных слишком большой и громоздкий, но примеры в вопросе являются его частью, и, если хотите, вот еще несколько .
Джон

Ответы:

570

Вот краткое решение, которое избегает регулярных выражений и медленных циклов в Python:

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

Посмотрите ответ сообщества Wiki, начатый @davidism для результатов теста. В итоге,

Решение Дэвида Чжана - явный победитель, опережающий всех остальных по крайней мере в 5 раз для большого набора примеров.

(Слова этого ответа, а не мои.)

Это основано на наблюдении, что строка является периодической тогда и только тогда, когда она равна нетривиальному вращению самой себя. Спасибо @AleksiTorhamo за понимание того, что мы можем затем восстановить основной период из индекса первого появления sin (s+s)[1:-1], и за информирование меня оstartend аргументах и аргументах Python string.find.

Дэвид Чжан
источник
19
Вы можете расширить это, чтобы найти самую короткую повторяющуюся подпоследовательность, используя .find()или .index()вместо in, например,. (s+s).find(s, 1, -1),
Алекси Торхамо
11
Кроме того, я думаю, что (s+s).find(s, 1, -1)это будет (очень немного) быстрее, чем (s+s)[1:-1].find(s), по крайней мере, для больших строк, так как нарезка означает, что вы должны создать еще одну копию (почти) всей строки.
Алекси Торхамо
13
Это как если вы возьмете синусоидальную или косовскую волну из периодической функции и сместите ее вправо. Поскольку он полностью периодический, волны в конечном итоге будут идеально совпадать ... Математические параллели с этим решением просто феноменальны. :) Я хотел бы дать вам + ∞ голосов.
Шашанк
6
Недавнее обновление Гвидо до PEP 8 уместно здесь: «Будьте последовательны в операторах возврата. Либо все операторы возврата в функции должны возвращать выражение, либо ни один из них не должен. Если какой-либо оператор возврата возвращает выражение, любые операторы возврата, где нет значения return должен явно указывать это как return None, и в конце функции должен присутствовать явный оператор return (если он доступен). "
Ноль Пирей
8
@WayneConrad Возьмите строку, скажем, выскочив "abcd"из символа справа, и вставьте ее обратно влево, чтобы получить "dabc". Эта процедура называется вращением строки вправо на 1 символ . Повторите nвремя, чтобы повернуть строку вправо на nсимволы. Теперь обратите внимание, что если у нас есть строка kсимволов, вращение вправо на любое кратное число kоставляет строку без изменений. Нетривиальным вращение струны один персонаж которого число не кратно длине струны.
Дэвид Чжан
181

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

import re

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

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+$делится на три части:

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

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

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

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

Ноль Пирей
источник
6
Я понятия не имею, почему этот краткий двухсторонний лайнер не является самым популярным ответом. Другие ответы неплохие, но этот гораздо лучше. (Он может использовать часто клеветническое регулярное выражение , но я могу проверить это гораздо проще, чем другие гораздо более длинные ответы, которые полны вложенных блоков, потенциальных опечаток, ошибок типа «один на один» и т. Д.) Ну, хуже, лучше, лучше Я предполагаю.
Пол Дрейпер
9
Я думаю, что для этого есть две основные причины: 1) некоторые программисты предпочитают математику больше, чем регулярные выражения, и 2) поскольку изменение длины и характера входных строк заставляет разные ответы увеличивать производительность, супер-длинные строки в крайнем случае (которые могут даже не отображаться в реальных данных) делают это решение неоптимальным.
TigerhawkT3
иногда вы сталкиваетесь с предрассудками в отношении регулярных выражений. У меня было 2 менеджера, которые запрещали использование регулярных выражений, потому что они слышали, что регулярные выражения - неподходящий инструмент для работы. За исключением переписки, они продолжили, попросив меня реализовать механизм регулярных выражений
joojaa
1
@PaulDraper: Угадай, что регулярное выражение делает за кулисами? он анализирует строку и сохраняет каждый элемент, пока не будет найдено возможное совпадение повторного ввода. То же самое, что OP заявляет как слишком медленный. просто потому, что это 2 лайнера, выигрыша в производительности нет.
Dhein
2
@Zaibis, я бы обычно согласился, но это и самое короткое, и самое быстрое решение ( stackoverflow.com/a/29482936/1212596). За исключением David, который был опубликован после того, как я сделал этот комментарий. Мне действительно нравится подход Дэвида (умный!).
Пол Дрэйпер
90

Вы можете сделать замечание, что для строки, которая будет считаться повторяющейся, ее длина должна делиться на длину повторяющейся последовательности. Учитывая это, вот решение, которое генерирует делители длины от 1до 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

РЕДАКТИРОВАТЬ: В Python 3, /оператор изменился на деление с плавающей запятой по умолчанию. Чтобы получить intделение от Python 2, вы можете использовать //вместо этого оператор. Спасибо @ TigerhawkT3 за то, что вы обратили на это мое внимание.

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

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

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

Shashank
источник
3
Это решение удивительно. Вы можете изменить метод делителей так, чтобы он следовал шаблону продукта-потребителя. Так что это дает результаты, как они найдены. Будет позором, если это не самый высокий ответ. Все остальное - грубая сила.
Джастин Даниелсон
3
@JustinDanielson Возвращает объект генератора, созданный из выражения генератора, который является неявным производителем :). Он будет лениво оценивать делители.
Шашанк
1
Оу. Я этого не знал. Ну, тогда еще лучше. : D Я понимаю, почему вы хотите избежать sqrt, но вы можете использовать n / 2 в качестве верхней границы для диапазона делителей.
Джастин Даниелсон
1
@JustinDanielson Спасибо за предложение, верхняя граница диапазона теперь (n/2)включена.
Шашанк
1
Если n / 2в divisors()быть n // 2?
TigerhawkT3
87

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

Некоторые функции были изменены для работы с 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

Корпус 1 граф


Корпус 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

Корпус 1 граф


Корпус 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

Корпус 3 граф


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

давидизм
источник
37

Решение без регулярных выражений:

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

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

Тестовое задание:

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

Результаты:

009
2547
abcde
None
None
None
TigerhawkT3
источник
Разве это не решение грубой силы?
Джастин Даниелсон,
7
@JustinDanielson Да. Но решение, тем не менее.
Точка погружения
3
Я наблюдаю от 1e-5 до 3e-5 секунд для коротких строк, от 3e-5 до 4e-5 секунд для успешных длинных (1000 символов) строк и чуть меньше миллисекунды для неудачных длинных строк (наихудший случай) , Таким образом, тысяча 1000-символьных строк займет около секунды. По сравнению с математическим ответом это находит совпадения в 10 раз быстрее, но терпит неудачу в 3 раза дольше.
TigerhawkT3
repeat('aa')возвращаетсяNone
Том Корнебиз
2
len(string[0:i])всегда равно i(в данном случае как минимум). Замена их, а также сохранение len(string)и string[0:i]в переменных может ускорить процесс. Также ИМО, это отличное решение,
круто
24

Сначала разделите строку пополам, если это дубликат «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

Возвращает самое короткое совпадение или None, если совпадения нет.

davidism
источник
16

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

Обратите внимание, это может быть медленнее , в общем случае (UPD: и гораздо медленнее) , чем другие решения , которые зависят от количества делителей n, но как правило , найти не удается раньше, я думаю , что одна из плохих случаев для них будет aaa....aab, где есть n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a«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
Риад
источник
Вы prefix_function()не действует Python: у вас есть недостающие колоны на ваши whileи ifзаявлениях, а &&вместо and. После исправления, это не сUnboundLocalError: local variable 'i' referenced before assignment из-за линии for i in range(i, n):.
Ноль Пирей
Спасибо :-) Если вы можете собрать функцию, которая использует ваш, prefix_function()чтобы вернуть аналогичные результаты для других ответов - либо самая короткая подстрока илиNone - я включу ее в пересмотренный тест, который я собираю.
Ноль Пирей
@ZeroPiraeus, на самом деле работает нормально, я просто назвал это неправильно
RiaD
16

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

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делу.

Антти Хаапала
источник
Это решение действительно практически идентично моему оптимизированному. Я вижу, что у вас есть rangeпредел length//2, как и у меня - вы должны изменить его на, length//2+1если вы хотите ловить строки, которые в точности удваиваются (например 'aabaab').
TigerhawkT3
И теперь они идентичны! \ o / Мне нужно больше внимания уделять оптимизации в будущем, но я рад, что сам алгоритм был надежным.
TigerhawkT3
15

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

Для подстрок, sначинающихся с нулевого индекса, длиной от 1 до 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"
Сакшам Варма
источник
Теперь, когда я внимательно посмотрю на это, оно кажется почти идентичным моему изначально опубликованному (до каких-либо изменений) решению, с единственной разницей, заключающейся в сохранении длины и подстроки. Я думаю, у меня был довольно хороший алгоритм. : P
TigerhawkT3
@ TigerhawkT3 Да, действительно! :)
Сакшам Варма
9

Я начал с более чем восьми решений этой проблемы. Некоторые были основаны на регулярном выражении (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 с помощью оператора умножения и сравнения строк очень оптимизировано.

Логика Найт
источник
Совсем неплохо :-) Тест работает на Python 3.4 (частично потому, что OP не указывает версию, и это то, что все должны использовать, и частично потому, что он использует новый statisticsмодуль), поэтому мне пришлось изменить ваши /s на //s и заменить xrange()на range()(который ведет себя как 2.x xrange()в 3.x).
Ноль Пирей
Вот изменения в тесте, так что вы можете просмотреть мои изменения, кстати.
Ноль Пирей
Спасибо ноль Это было быстро. Результаты оказались немного ниже моих прогнозов. Я подозреваю, что методы, которые я использовал для скорости в Python 2.7, не очень эффективны в Python 3.4. Ну да ладно - веселое и познавательное упражнение.
Логика Найт
//в 3.x - целочисленное деление (точно так же, как в 2.x /), в то время как 3.x - /это деление на числа с плавающей точкой (что, я уверен, будет намного медленнее, даже если оно не нарушит ваше решение, вызвав попытку использования Поплавок в качестве индекса). Как уже упоминалось, 3.x - range()это то же самое, что и 2.x xrange(); range()в 3.x не существует эквивалента 2.x. Так что я не думаю, что это является причиной какого-либо несоответствия между эталонным тестом и любыми временами, которые вы сделали. Вероятно, просто 3.x медленнее, чем 2.x (или, возможно, ваша машина быстрее, чем моя).
Ноль Пирей
Когда у меня будет время, я внимательно посмотрю на различия во время выполнения между Python 2 и Python 3.
Logic Knight
2

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

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'
Петр Дабковский
источник
Спасибо :) Я не очень оптимизировал это все же. Я просто хотел представить другой подход, потому что другие ответы направлены на поиск шаблона, а мой подход нацелен на доказательство отсутствия шаблона :). Поэтому для случайных строк мой алгоритм должен работать намного быстрее.
Петр Дабковски,
0

В ответе Дэвида Чжана, если у нас есть какой-то круговой буфер, это не сработает: 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'
sachinruk
источник
-1

Вот код на 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' не найдено повторяющейся подстроки

Srivishnu
источник