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

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

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

тогда мне бы хотелось, чтобы значение & quot;helloworld& Quot; быть возвращенным.

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

 Kristopher Micinski18 июн. 2012 г., 22:14
Я не знаю, есть ли регулярное выражение для решения этой проблемы. этоcan't быть регулярным выражением, но Python может иметь нерегулярное расширение, которое делает что-то вроде этого. В общем случае это проблема LCS, которая может быть решена с помощью динамического программирования:en.wikipedia.org/wiki/Longest_common_subsequence_problem

Ответы на вопрос(6)

from collections import Counter

def Longest(string):

    b = []
    le = []

    for i in set(string):

        for j in range(Counter(string)[i]+1): 
            b.append(i* (j+1))

    for i in b:
        if i in string:
            le.append(i)


    return ([s for s in le if len(s)==len(max( le , key = len))])

начинающейся с каждой позиции во входной строке. 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)
 Snesticle19 июн. 2012 г., 15:35
Я действительно люблю это решение, но, к сожалению, мои строки обычно слишком велики. Я, однако, держу пари, что ваш ответ будет очень полезен для многих людей, попадающих сюда через Google, так как он действительно решает оригинальный пример, который я привел довольно приятно.
Решение Вопроса

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

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

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

 24 дек. 2012 г., 07:11
Это первый раз, когда я вижу, как кто-то публикует полезный / нереференциальный ответ на любой вариант LCS. Спасибо за ссылку на библиотеку.
 18 июн. 2012 г., 22:22
@ KonradRudolph - я не знаю ни одного "простого" алгоритмы построения суффиксных деревьев за линейное время. Два известных мне алгоритма (алгоритм Укконена и алгоритм DC3) чрезвычайно сложны и не имеют очевидных доказательств правильности. Тем не менее, если я ошибаюсь по этому поводу, я бы хотел быть исправленным!
 18 июн. 2012 г., 22:25
Я согласен с тем, что доказательства не являются тривиальными. Но существуют псевдокоды для алгоритма Укконена, которые легко адаптировать. Кроме того, хотя алгоритмы с линейным временем трудно найти, существуют тривиально производные алгоритмы нелинейного построения, которые, тем не менее, хорошо работают на практике.
 18 июн. 2012 г., 22:20
& # x201C; общеизвестно, трудно построить & # x201D; & # X2013; чего-чего?

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

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

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

Edit: если вы чувствуете, что имеете дело со случайным вводом, а общая подстрока должна быть небольшой длины, лучше начинать (если вам нужна скорость) небольшие подстроки и останавливаться, когда вы не можете найти ни одной, которая появляется по крайней мере 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) 

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

 19 июн. 2012 г., 00:06
@MattCoughlin, наихудший случай, когда число подстрок смотрит на квадратик 1-го взгляда: это сумма (len (a) - ([len (a) / times] - i) +1), где i работает от 0 до [len ( а) / К], которая есть O (len (a) ^ 2). Затем вы строите частоту на каждой подстроке, которая является линейной на подстроке. Таким образом, это может быть O (len (a) ^ 3) в конце, пожалуйста, исправьте меня, если я ошибаюсь. Вы можете сэкономить некоторые операции в Counter, поскольку вам не нужен весь дистрибутив, а только, чтобы знать, что max freq равно & gt; = 3. Если вы знаете, что имеете дело со случайным вводом, лучше начать с небольших строк. Таким образом, на практике это должно быть довольно быстро
 18 июн. 2012 г., 23:45
@PaulMcGuire точно
 18 июн. 2012 г., 23:48
Я пытаюсь сделать что-то похожее в противоположном направлении (от маленького к большому). Есть идеи, какова сложность времени для вашего подхода?
 18 июн. 2012 г., 23:44
То есть каждый набор подстрок M строится долго, начиная сM=len(a)/N (где N - минимальное количество повторений) и подсчитайте количество повторений каждого. Если ни одна из подстрок не имеет числа вхождений & gt; = N, вычтите 1 из M и повторите попытку. Да?

которая пришла в голову, - это поиск с постепенно увеличивающимися регулярными выражениями:

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

 02 июл. 2016 г., 08:08
не работает сbanana, ответ должен бытьana 2 times

Ваш ответ на вопрос