alex_ita's blog

By alex_ita, history, 2 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

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


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).