**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â€¦

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

Complexity(nlog(n))!

hope that helps

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

http://www.careercup.com/question?id=15430756 there is a discussion here also check it out.

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