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

Carvia Tech | May 04, 2019 at 11:40 AM | 3 views | Python Coding Problem


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
aada

Top articles in this category:
  1. Top 100 interview questions on Data Science & Machine Learning
  2. Write a program for Hailstone Sequence in Python
  3. Write a program to find if a number is Lychrel Number in Python
  4. Write a program to check if the given word is Isogram & Pair isogram in python
  5. python problem 1: find the runner-up score
  6. Introduction to Python 3.6 & Jupyter Notebook
  7. Creating custom Keras callbacks in python


Find more on this topic:
Machine Learning image
Machine Learning

Data science, machine learning, python, R, big data, spark, the Jupyter notebook, and much more

Last updated 1 month ago


Recommended books for interview preparation:
You may also be interested in..
Generic placeholder image
ebook PDF - Cracking Spring Microservices Interviews for Java Developers
You may also be interested in..
Generic placeholder image
ebook PDF - Cracking Java Interviews v3.5 by Munish Chandel

This website uses cookies to ensure you get the best experience on our website. more info