Build a suffix tree from a string.
While creating the suffix tree, count re-occurrences of every substring and save it on the number of occurrences on the node.
Then do a BFS search on the tree (from shorter to longer strings) and find the substring with the highest count.
The time to construct suffix tree is O(n). BFS search find all the substring and return substring with highest count which required O(k), k is the number of substrings found from suffix tree. So the worst case complexity is O(n+k) or the complexity is O(nk)?