Given a string S find the longest repeated substring non overlaps. 1 <= |S| <= 50,000 Input: ABBBB output: BB
I'm trying to solve a problem like this, after thinking some time I came up with this solution using suffix array:
pos[i] -> sorted suffix array lcp[i] -> longest common prefix between i-th suffix and (i-1)-th suffix lcp2[i] -> like lcp but without overlaps -> lcp[i] = min(l p[i], abs( pos[i] - pos[i - 1] ) ) ans = max( lcp2[i] ) for 1 <= i < |S|
my approach was working for some cases but it fails for the test I wrote before.
I could think in a brute force solution which I think its some obvious:
For all repeated substring SUB, try all substring of SUB and test if have overlaps.
Do you have a better way?