What would be the best approach (performance-wise) in solving this problem? I was recommended to use suffix trees. Is this the best approach?
Have a look at http://en.wikipedia.org/wiki/Suffix_array as well - they are quite space-efficient and have some reasonably programmable algorithms to produce them, such as "Simple Linear Work Suffix Array Construction" by Karkkainen and Sanders