Longest Repetitive Substring


  • 0

    Given a string, find the longest repetitive substring.

    Example:

    input "banana", output "ana".
    Explanation: "ana" is repeated twice.

    input "ababab", output "abab".
    Explanation: "abab" is repeated twice.


  • 0

    From the example about I see that the longest repeative substring shouldn't be substring of each of the pattern. Is it true?


  • 1

    Isn't that implied? The longest repetitive substring cannot be substring of other repetitive substrings which are shorter in length. The longest repetitive substring, is however, guaranteed to be a substring of longer substrings (each of which will occur only once throughout the complete string).

    A clear definition of the question is:
    The Longest Repetitive Substring is a substring which occurs atleast twice in the original string and is longer than all other such substrings.

    For more reading, Wikipedia has a good entry: https://en.wikipedia.org/wiki/Longest_repeated_substring_problem


  • 0

    @babhishek21 thank you very much. It was my mistake,


  • 0

    Suppose that it is not expected to build suffix tree in the interview ? Then we can create suffix array or to build trie with all suffixes and to find longest repetitive substring


  • 0
    R

    I dind't find anything better than a prefix tree for this problem.

    Follows a possible implementation:

    #!python3
    
    class Node:
       def __init__(self):
          self.nodes = [None] * 256
    
       def insert(self, text):
          node = self
          result = 0
          while node:
             head, tail = text[0], text[1:]
             next = node.nodes[head]
             if next:
                result += 1
                node = next
             else:
                next = Node()
                node.nodes[head] = next
                if tail:
                    node = next
                    text = tail
                else:
                    node = None
          return result
    
    
    def max_repeated_substring(text):
        if not text:
           return ''
        text = text.encode()
        root = Node()
        bestCount = 0
        best = ''
        for i in range(len(text)):
           count = root.insert(text[i:])
           if count > bestCount:
              best = text[i:i + count]
              bestCount = count
        return best
    
    

  • 1
    A

    Excellent slides to understand how to tackle such problems:: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.