Making LCP from Suffix Array

Question

I am learning about Suffix arrays and Successful learnt how to make a Suffix array in O(nlognlogn) times From this Tutorial.

Now i am wondering How would i create LCP Array from my Suffix Array in O(nlogn) time or better obviously i know the O(n*n) approach. I want something Better

I could not find any good online resource Please Help me so i could completely learn this topic and it will helps the other.

Thanks

Answer 1

The simplest O(n) approach is to loop from left to right (longest to shortest) suffix. Then note that if the longest common prefix (LCP) between the current suffix at i and its neighbor in the sorted suffix array table is h, the next LCP at i + 1 can decrease by at most one. This is because the next suffix is equivalent to advancing the first character by one, so we could achieve h - 1 at least just by advancing the neighbor by one character as well. If a different suffix happens to fall in between, it will still share a prefix of at least h - 1.

This allows us to make an O(n) amortized algorithm by advancing forward as far as necessary, and then advancing back by one when moving on to the next index.

Correct (afaik) implementation: https://sites.google.com/site/indy256/algo/suffix_array

Answer 2

You can make LCP array from suffix array in O(n) time using kasai's alorithm

construction of lcp array from suffix array