CODEWITHSUNDEEP
algorithmsuffix-array
user4996457
user4996457

Reputation: 161

Making LCP from Suffix Array

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

Upvotes: 2

Views: 1207

Answers (2)

pavaniiitn
pavaniiitn

Reputation: 311

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

construction of lcp array from suffix array

Upvotes: 1

Johnny Ho
Johnny Ho

Reputation: 61

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

Upvotes: 3

Related Questions