finally I solved this using DC3 algorithm (a linear suffix array construction algoritm). it's supposed to run in O(n) time. my java solution runs in ~1.17 but my main language is scala and in scala (the escat same algorithm) is above 2 sec.
is it possible to solve this with KMP faster? i couldn't find a correct solution.