Substring Problem

Given: A string.
To find: The longest substring that occurs more than once if overlapping is allowed.

Algorithms and Programming: Problems and Solutions By Alexander Shen
There is a very beautiful explaination to this problem in this book. the solution is implemented with suffix arrays.
sort the elemnts of the suffix array.
Then if a string X appears twice then it is prefix of two suffixes of Y and both X are neibhours.
find out all such string and print the longest of them…:slight_smile:


I think Best Algorithm for this problem is RabinKarp + BinarySearch.

hope that helps

1 Like

another approach will be using suffix trees

So Build a suffix tree. Maintain a count variable at every node of the tree to track the number of time the node was parsed when inserting a suffix. Remember to put zero for the first level as single letters will not be considered as substrings. Once such an suffix tree is created, perform a depth first search to find a node with highest count you have your substring there is a discussion here also check it out.

1 Like

@solve that is a good approach too but suffix array solves problem in O(n) if n is length of string.

1 Like