Write a python program to find Largest Substring that occurs more than once

Upasana | May 04, 2019 | 1 min read | 49 views | Python Coding Problems

Largest Substring

you need to identify the largest substring that occurs more than once within a larger string. You will be given a list of strings. Each string will consist of some random set of lowercase letters of at least one character and at most 100 characters. For example, given the string “abbbcdaabbbczaabbbc” we can identify several substrings that occur more than once:

ab occurs 3 times
bbb occurs 3 times
aabbbc occurs 2 times

def get_longest_substring(str):
    n = len(str)
    l = [[0 for x in range(n + 1)]
            for y in range(n + 1)]
    res = ""
    res_length = 0
    idx = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                l[i - 1][j - 1] < (j - i)):
                l[i][j] = l[i - 1][j - 1] + 1
                if (l[i][j] > res_length):
                    res_length = l[i][j]
                    idx = max(i, idx)

            else:
                l[i][j] = 0
    if (res_length > 0):
        for i in range(idx - res_length + 1,idx + 1):
            res = res + str[i - 1]

    return res

print(get_longest_substring("aadaghgdjdjdjaada"))

Output