@AndreyRaf13

Проверка на overlapped part в алгоритме «Longest Repeated Substring»?

Реализовываю решение задачи:
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, но эти строки пересекаются. Как дополнить этот код, чтобы он проверял, не пересекаются ли подстроки?
  • Вопрос задан
  • 52 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы