Given a string, find the longest repetitive substring.
input "banana", output "ana".
Explanation: "ana" is repeated twice.
input "ababab", output "abab".
Explanation: "abab" is repeated twice.
From the example about I see that the longest repeative substring shouldn't be substring of each of the pattern. Is it true?
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
@babhishek21 thank you very much. It was my mistake,
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
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, 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
Excellent slides to understand how to tackle such problems:: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.