Answer the question
In order to leave comments, you need to log in
Check for overlapped part in "Longest Repeated Substring" algorithm?
I am solving the problem:
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
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'))
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question