Suffix Tree or something else to compute LCP array
Hello. I'm trying to do this task: POLSKI SPOJ - Problem LCP: test your programming skills on-line
Short translate: We have T - test numbers and then in next T lines words. The task is to create suffixes of each word and then compute LCP array for each of them. We sort suffixes assuming that on the end of each of them is the greatest unique character. So if we have word ababa we have following order of suffixes:
And the LCP array of this word is: 3 1 0 2.
I tried to use suffix arrays and compute LCP based on them, but i got time limit exceeded, so i need something faster. I was trying to make suffix tree using Ukkonen algorithm, but I failed. I will be grateful for every help.