alex_ita's blog

Suffix array problem
By alex_ita, history, 6 years ago, In English

Hello everyone!
I've recently learned Suffix array and how to build LCP array (using this code). I've solved a few problems, but then I found this one and couldn't solve it.
Can anyone help me how to solve Jarvis and LCP using that code?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hello,

After building suffix array and LCP array you can find |LCP| of two suffixes s and t by formula ans=min{id[s]<=k<id[t]|lcp[k]}, where id[x] is index of suffix x in suffix array. Obviously if id[s]>id[t] we should swap them. Using sparse table we can answer such queries in O(1). To solve Jarvis and LCP first build string H= S[1]+$+S[2]+#+...+S[n] (separate them by different characters). Now LCP of two strings is equal to LCP of corresponding suffixes in string H. To find how many times it occurs in all strings we can just find how many times it occurs in string H. All suffixes that have prefix equal to some string are continuous subsegment of suffix array. To find left and right bound of it we can run two binary searches to find lexicographically lowest and largest such suffix. Answer is id[highest]-id[lowest]+1.

Time complexity is O(NlogN).

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have 2 questions. 1. How would I concatenate 10000 strings with different characters? Is there some observation here that I am missing? 2. And while running binary search what would the low and high bounds be?

    → Reply