Suffix Tree: Longest repeating substring implementation

Question

I have implemented a suffix tree, which is not compressed. I wanted to know how to solve the problem of finding the longest repreating substring in a string. I know that we have to find the deepest internal node with two children, but how can be code this. Also, how do we know what the longest repeating substring is. I am interested in the code in JAVA. Pls give java implementation. For reference, my TrieNode looks like

class TrieNode{

char ch;
LinkedList<TrieNode> child;

}

Answer 1

It's only the deepest node with 2 children if you store an end of string byte.

To find the longest substring you'll need to do a depth first search, keeping a reference to the deepest node with 2 or more children and it's depth. This is easiest to do with a recursive function.

Answer 2

The algorithm of Aho- Corasick http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

Answer 3

To find deepest node, one can also do BFS and select node which has maximum level. I think node with maximum level is also the deepest node.then you can check if it has 2 children . else go higher. not sure if this will work though. any comments pps?