yashi's blog

Longest Repeated Substring Using Suffix Array [SOLVED]
By yashi, history, 9 years ago, In English

Hello there,

I was trying to solve this problem on Hackerearth the problem asks for the length of the longest substring which is repeated at least K times, 1 <= K <= |S| <= 10^6

I built the suffix array of the string and built the LCP array then get the maximum element among the minimum elements in all possible consecutive segments of length K-1 in the LCP array, Thus, if the LCP array was [0,1,2,3,2,3] and K was 4 then we have :

1. [0,1,2] min is 0
2. [1,2,3] min is 1
3. [2,3,2] min is 2
4. [3,2,3] min is 2

Now the maximum element is 2 and this is the answer, My solution keeps getting WA on some test files, and unfortunately editorial page has no explanation about the solution, just two codes, one uses an absolutely different idea where it uses hashing and binary search (No idea!!) and the other one slightly uses the same idea using suffix tree instead but it's so messy and couldn't track it down.

Here's my code .
Any help would be highly appreciated .

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

3 12

abcdefabcdea

I think you should not use a set to find the sliding window maximum. maybe use a monotone queue instead.

UPD: I am not quite sure about the output, please notify me in case my test case produces correct answer.

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

    My previous code outputs 4 where the the correct output is 1 .

    I was stupidly using the set to get the sliding window maximum where I was erasing the minimum element in each step instead of erasing the first element of the segment .

    I used a segment tree and got AC in 15 seconds :D .

    Now I modified the first code and got AC without a segment tree and it passed even faster :D . (13 seconds)

    Thanks so much Nezzar I do appreciate your help .

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

    Just out of curiosity, I have no idea how to do that using a monotone queue, it would be great if you could enlighten me .

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).

→ Reply