Longest Repeated Substring Using Suffix Array

Revision en1, by yashi, 2016-03-28 15:56:40

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 .

Tags suffix array, lrs, strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English yashi 2016-03-28 18:28:55 9
en1 English yashi 2016-03-28 15:56:40 1260 Initial revision (published)