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…
2 Likes
I think Best Algorithm for this problem is RabinKarp + BinarySearch.
Complexity(nlog(n))!
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
Given a string, find the longe | CareerCup 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