Найти самую длинную повторяющуюся последовательность в строке

Мне нужно найти самую длинную последовательность в строке с оговоркой, что последовательность должна повторяться три или более раз. Так, например, если моя строка:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

то я хотел бы вернуть значение « helloworld ».

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

  • регулярное выражение python более одного раза соответствует индексу строки поиска
  • Как заменить первое вхождение регулярного выражения в Python?
  • Разделить строку запятыми, кроме случаев, когда в скобках
  • Использование регулярного выражения для запятой выделяет большое количество в системе нумерации южной Азии
  • Python 2.6+ str.format () и регулярные выражения
  • Почему это так долго, чтобы соответствовать? Это ошибка?
  • Обратное слово в Vim
  • Django - как получить содержимое тега {% block%} из шаблона
  • 5 Solutions collect form web for “Найти самую длинную повторяющуюся последовательность в строке”

    Эта проблема является вариантом самой длинной повторяющейся задачи подстроки и существует алгоритм O (n) -time для ее решения, который использует деревья суффикса . Идея (как было предложено Wikipedia) состоит в том, чтобы построить дерево суффиксов (время O (n)), аннотировать все узлы в дереве с числом потомков (время O (n) с использованием DFS), а затем найти самый глубокий узел в дереве с по меньшей мере тремя потомками (время O (n) с использованием DFS). Этот общий алгоритм занимает время O (n).

    Тем не менее, суффиксные деревья, как правило, трудно построить, поэтому вы, вероятно, захотите найти библиотеку Python, которая реализует деревья суффиксов для вас, прежде чем пытаться выполнить эту реализацию. Быстрый поиск Google включает эту библиотеку , хотя я не уверен, что это хорошая реализация.

    Надеюсь это поможет!

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

    from collections import defaultdict def getsubs(loc, s): substr = s[loc:] i = -1 while(substr): yield substr substr = s[loc:i] i -= 1 def longestRepetitiveSubstring(r, minocc=3): occ = defaultdict(int) # tally all occurrences of all substrings for i in range(len(r)): for sub in getsubs(i,r): occ[sub] += 1 # filter out all substrings with fewer than minocc occurrences occ_minocc = [k for k,v in occ.items() if v >= minocc] if occ_minocc: maxkey = max(occ_minocc, key=len) return maxkey, occ[maxkey] else: raise ValueError("no repetitions of any substring of '%s' with %d or more occurrences" % (r,minocc)) 

    печатает:

     ('helloworld', 3) 

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

     from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1)[::-1]: substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]>=3: seq=freqs.most_common(1)[0][0] break print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

    Результат:

     >>> sequence 'helloworld' of length 10 occurs 3 or more times 

    Редактирование: если у вас есть ощущение, что вы имеете дело со случайным вводом, а общая подстрока должна быть малой длины, вам лучше начать (если вам нужна скорость) с небольшими подстроками и остановиться, когда вы не можете найти какие-либо изображения, появляющиеся на минимум 3 раза:

     from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1): substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]<3: n-=1 break else: seq=freqs.most_common(1)[0][0] print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

    Тот же результат, что и выше.

    Первой идеей, которая пришла на ум, является поиск с более широкими регулярными выражениями:

     import re text = 'fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' largest = '' i = 1 while 1: m = re.search("(" + ("\w" * i) + ").*\\1.*\\1", text) if not m: break largest = m.group(1) i += 1 print largest # helloworld 

    Код успешно выполнен. Сложность времени, по-видимому, не меньше O (n ^ 2).

    Если вы отмените входную строку, затем подайте ее в регулярное выражение типа (.+)(?:.*\1){2}
    Он должен дать вам длинную строку, повторяющуюся 3 раза. (Обратный захват группы 1 для ответа)

    Редактировать:
    Должен сказать отменить этот путь. Это зависит от первого матча. Если он не тестировался по отношению к длине текущей длины до максимальной длины, в итеративном цикле регулярное выражение не будет работать для этого.

    Python - лучший язык программирования в мире.