Longest repeated substring problem
This problem can be solved in linear time and space [ Θ(n) ] by building a suffix tree for the string, and finding the deepest internal node in the tree. 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. The problem of finding the longest substring with at least occurrences can be solved by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least leaf descendants that have no children.
In the figure with the string "ATCGATCGA$", the longest substring that repeats at least twice is "ATCGA".
- Allison, L. "Suffix Trees". Retrieved 2008-10-14.
- C implementation of Longest Repeated Substring using Suffix Tree
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|