Longest Repeated Substring Using Suffix Array

Правка en1, от 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 .

Теги suffix array, lrs, strings

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский yashi 2016-03-28 18:28:55 9
en1 Английский yashi 2016-03-28 15:56:40 1260 Initial revision (published)