I wonder if there's an easy way to solve this problem using suffix automaton. There's a linear solution for this problem using suffix tree (link to a much harder version of a problem).