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

Ответ 1

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

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

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

Ответ 2

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

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

Начните с конца, подсчитайте частоту и остановите, как только самый частый элемент появится 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) 

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

Ответ 4

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

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

Ответ 5

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

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