Longest repeated substring problem

by building a suffix tree for the string (with a special end-of-string symbol like '$' appended), and finding the deepest internal node in the tree with more than one child.

Depth is measured by the number of characters traversed from the root.

The string spelled by the edges from the root to such a node is a longest repeated substring.

To avoid overlapping repeats, you can check that the list of suffix lengths has no consecutive elements with less than prefix-length difference.

In the figure with the string "ATCGATCGA$", the longest substring that repeats at least twice is "ATCGA".