3

Реализовываю решение задачи:

You have to return a substring length. You need to find a substring that repeats more than once in a given string. This reiteration shouldn't have overlaps. For example, in a string "abcab" the longest substring that repeats more than once is "ab", so the answer should be 2 (length of "ab")

Input: String.

Output: Int.

Example:

double_substring('aaaa') == 2 double_substring('abc') == 0 double_substring('aghtfghkofgh') == 3 # fgh

Вот какое решение я написал, исходя из найденого мной алгоритма:

"For each two adjacent suffixes on the sorted suffix array, count the length of the common prefix (Note: should avoid counting the overlapped part). The longest repeated prefix appearing first on the original input string is the result."

Код:

def function(string):
    suffixes = sorted([string[i:] for i in range(len(string))])
    print(suffixes)

    longest_prefix = 0

    for i in range(0, len(suffixes) - 1):
        first_suffix = suffixes[i]
        second_suffix = suffixes[i+1]
        counter = 0
        for j in range(0, min(len(first_suffix), len(second_suffix))):
            if first_suffix[j] == second_suffix[j]:
                counter += 1
            else:
                break

        if counter > longest_prefix:
            longest_prefix = counter
    return longest_prefix

print(function('aghtfghkofgh'))

Этот код плохой тем, что он не учитывает overlapped parts. То есть для строки "аааа" он возвратит 3, но эти строки пересекаются. Как дополнить этот код, чтобы он проверял, не пересекаются ли подстроки?

2 ответа 2

1

Могу предложить такое решение:

def double_substring(string):
    length = len(string)
    limit = int(length / 2)
    for max_ in range(limit, 0, -1):
        overlaps = []
        for i in range(0, 1+length-max_*2):
            offset = i + max_
            part = string[i:offset]
            if part in overlaps:
                continue
            index = string.find(part, i + 1)
            while index > 0:
                if index < offset:
                    overlaps.append(part)
                    break
                offset = index + max_
                index = string.find(part, index + 1)
                if index < 0:
                    print(part)
                    return max_
    return 0


print(double_substring('aaaa'))
print(double_substring('abcab'))
print(double_substring('aghtfghkofgh'))
print(double_substring('abc'))
print(double_substring('abbaabbadabbaabba'))

Рассуждения такие:

  • максимальная длина повторяющейся непересекающейся подстроки будет не более длины строки, деленной на 2;
  • так как мы ищем максимум, то начинаем поиск с максимальной строки, спускаясь до минимума. При нахождении - сразу выход из циклов;
  • оптимизируем перебор вложенного цикла до длины строки минус текущая длина подстроки, умноженная на 2;
  • ведём список пересекающихся подстрок, чтобы не нарваться при дальнейшем сканировании строки;
  • каждая подстрока в цикле проверяется на пересечение со своей следующей копией

И, кстати, правильный ответ для double_substring('aaaa') это 1, так как aa пересекается с собой даже два раза: (a(a)a)a, a(a(a)a)

0

Для отслеживания пересекающихся частей был использован класс collections.deque.

from collections import deque

def slide(string, size):
    dq = deque(maxlen=size)
    for pos in range(len(string) - size + 1):
        ch = string[pos:pos + size]
        if not (ch in dq and pos % size > 0):
            yield ch
        if len(dq) == size:
            _ = dq.popleft()
        dq.append(ch)

def longest(string):
    up = len(string) // 2 + 1
    for size in range(up, 1, -1):
        d = dict()
        for ch in slide(string, size):
            d[ch] = d.get(ch, 0) + 1
            if d[ch] > 1:
                return ch, len(ch)
        d.clear()
    return '', 0

for s in ['aaaa', 'aaaaa', 'aaaaaa', 'abc', 'aghtfghkofgh']:
    subs, l = longest(s)
    print('строка: "{}", подстрока: "{}", длина: {}'.format(s, subs, l))

Результат:

строка: "aaaa", подстрока: "aa", длина: 2
строка: "aaaaa", подстрока: "aa", длина: 2
строка: "aaaaaa", подстрока: "aaa", длина: 3
строка: "abc", подстрока: "", длина: 0
строка: "aghtfghkofgh", подстрока: "fgh", длина: 3

Демо.

2
  • Для всех Ваших примеров с 'a' правильный ответ: подстрока 'a', длина 1. Также для строки abbaabbabbacd правильный ответ 'abb' длина 3, а не 'abba' длина 4 8 дек 2019 в 22:44
  • Было бы полезно, если бы Вы описали Ваш алгоритм... 8 дек 2019 в 22:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.