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

asked Jun 18, 2012 at 20:09

This problem is a variant of the longest repeated substring problem and there is an O(n)-time algorithm for solving it that uses suffix trees. The idea (as suggested by Wikipedia) is to construct a suffix tree (time O(n)), annotate all the nodes in the tree with the number of descendants (time O(n) using a DFS), and then to find the deepest node in the tree with at least three descendants (time O(n) using a DFS). This overall algorithm takes time O(n).

That said, suffix trees are notoriously hard to construct, so you would probably want to find a Python library that implements suffix trees for you before attempting this implementation. A quick Google search turns up this library, though I’m not sure whether this is a good implementation.

Another option would be to use suffix arrays in conjunction with LCP arrays. You can iterate over pairs of adjacent elements in the LCP array, taking the minimum of each pair, and store the largest number you find this way. That will correspond to the length of the longest string that repeats at least three times, and from there you can then read off the string itself.

There are several simple algorithms for building suffix arrays (the Manber-Myers algorithm runs in time O(n log n) and isn’t too hard to code up), and Kasai’s algorithm builds LCP arrays in time O(n) and is fairly straightforward to code up.

Hope this helps!

answered Jun 18, 2012 at 20:17

Use defaultdict to tally each substring beginning with each position in the input string. The OP wasn’t clear whether overlapping matches should or shouldn’t be included, this brute force method includes them.

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

prints:

('helloworld', 3)

answered Jun 18, 2012 at 21:36

Let’s start from the end, count the frequency and stop as soon as the most frequent element appears 3 or more times.

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)

Result:

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

Edit: if you have the feeling that you’re dealing with random input and the common substring should be of small length, you better start (if you need the speed) with small substrings and stop when you can’t find any that appear at least 3 time:

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) 

The same result as above.

answered Jun 18, 2012 at 21:31

The first idea that came to mind is searching with progressively larger regular expressions:

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

The code ran successfully. The time complexity appears to be at least O(n^2).

answered Jun 18, 2012 at 21:11

youth4everyouth4ever

1984 silver badges13 bronze badges

answered Mar 12, 2019 at 16:07

задан 6 ноя 2019 в 12:43

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

Регулярное выражение d+ ищет последовательности цифр, а re.findall вернет строки с результатом.

Останется список строк превратить в список длин строк и получить максимальное значение.

Пример:

import re

text = input("Введите строку: ")
items = re.findall('d+', text)
max_len = max(len(x) for x in items)
print(max_len)

Консоль:

Введите строку: 12 abcsd232 df12124 5555555
7

UPD.

Через цикл:

text = '12 abcsd232 df12124 5555555'
max_len = 0
cur_len = 0

for c in text:
    if c in '0123456789':
        cur_len += 1
    else:
        if cur_len > max_len:
            max_len = cur_len
        cur_len = 0

if cur_len > max_len:
    max_len = cur_len

print(max_len)  # 7

Или:

text = '12 abcsd232 df12124 5555555'
max_len = 0
cur_len = 0

for i in range(len(text)):
    c = text[i]
    if c in '0123456789':
        cur_len += 1
    elif cur_len > max_len:
        max_len = cur_len
        cur_len = 0

    # Конец строки
    if i == len(text) - 1 and cur_len > max_len:
        max_len = cur_len

print(max_len)  # 7

ответ дан 6 ноя 2019 в 12:57

input() всегда выдает строку, поэтому условие if type(xArr[index]) == int не выполнится никогда. Нужно его заменить, например, на такое:

if xArr[index] in "0123456789":

Второй if просто заменить на else и убрать оттуда break конечно же. То условие не делает ничего нужного.

ответ дан 6 ноя 2019 в 12:59

sdmntsdmnt

54 бронзовых знака

ответ дан 16 ноя 2022 в 11:10

Вот так можно переложить ваш код на простой “язык”!

print(‘Введите строку: ‘, end = ”)
text = input()
text += ”
count_s = 0
letter = 0

for symbol in text:
if symbol == ‘s’:
letter += 1
else:
if letter > count_s:
count_s = letter
letter = 0
print(‘Самая длинная последовательность: ‘, count_s)