k790alex's blog

By k790alex, 5 years ago, ,

Problem:

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?

Thanks.

• +3

 » 5 years ago, # |   +1 easy, if you know suffix automaton. just calculate first and last position in string for all states.
•  » » 5 years ago, # ^ |   0 thanks, I gonna read about suffix automaton.If the problem is to find the longest repeated substring (non-overlapping) repeted (al least / exactly) k times, suffix automaton works?
•  » » » 5 years ago, # ^ | ← Rev. 8 →   +1 yes, the sameupd i forgot about non-overlaping. with this condition i know solution only with O(Nlog2N) time instead of O(N)one more upd it is O(KNlog2N). but here was a discussion about similar problem with k=3, maybe helps.
•  » » » » 5 years ago, # ^ |   0 can you explain solution for k non-overlaping substrings?
•  » » » » » 5 years ago, # ^ | ← Rev. 5 →   0 big upd lets try again with yuzhou627's solution. after fixing LEN (in bs) and separating array to segments, for every segment make two sets: set of indexes and set of difference of consecutive pairs, for example for segment with indexes {1, 3, 4} it is {1, 2}. so, while in second set minimum
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   -8 It looks like greedy solution. We don't know which number we need to pop out from the first set (it can be 3 or 4). That's why I am not sure, what it will work. But probably after building the suffix array we can easily solve problem for each segment, using fenwick tree.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 i explained, please check for mistakes:)
 » 5 years ago, # |   0 hash maybe help
•  » » 5 years ago, # ^ |   0 how?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +11 Why is it downvoted?First, binary search over length. For fixed length L let's check if there is an answer of this length. For each substring of length L find it's hash. For each hash store first and last occurence. If for some hash first and last occurences are far enough from each other, answer for this length is true.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 This approach takes O(n^2 lg n) time: O(n) time to iterate over each substring of length k O(n) time to hash each substring O(lg n) time to binary search If you use a rolling hash, however, you can solve in O(n lg n) time (in the best case).
•  » » » » 4 years ago, # ^ |   0 have a look at the solution proposed by me below
 » 5 years ago, # | ← Rev. 2 →   0 Use binary search. When we check a length K, could it be the ans? We separate the array lcp[] into many groups, each contains continous elements of array lcp[] and all lcp[i]>= K, and we should check the max_index of suffix and min_index of suffix in each group to see if their difference is bigger than K.And it's done.:D
 » 4 years ago, # | ← Rev. 2 →   0 What test cases does your approach fail on?Edit: it fails for "aaaaa" (it returns "a")
 » 4 years ago, # |   +8 Here is my solution to this problem using binary search or string hashing.Observation : 1. If there exists such string having length x then there must be atleast one such string for all lengths < x. use this idea to binary search on the length. Fixed a length (say z) find hashes corresponding to each string of length z. There will be exactly n — z + 1 such hashes where n is the length of the given string. Keep one extra information with each hash that is starting index of this string in the given string. sort this vector of pairs now and iterate over it to find the maximum distance between the starting index of two string having equal hash value. This will help you in testing whether these two strings are overlapping or not. One you find the answer depending upon your answer you may proceed to any half of the binary search. complexity : O ( N * log(N) * log(N) )
•  » » 4 years ago, # ^ |   0 UPDATE : this solution will also work if you want to find the longest length substring which occurs k times in the original string and each of this k substrings of maximum length are non-overlapping.
•  » » 4 years ago, # ^ |   0 This works, but I'm not sure where you got the complexity of O(n * log^2(n)) from. If you're hashing a string, that will take O(n) time, so the complexity would be O(n^2 lg n). That being said, you could hash in constant time by using a rolling hash. The problem with that, however, is that you could run into collisions. The best case would be O(n lg n) though.
•  » » » 4 years ago, # ^ |   0 Of course it will use rolling hash. It's time complexity is O(nlg^2n) due to it's O(lgn) time sorting step.
•  » » » » 4 years ago, # ^ |   0 What sorting step?
•  » » » » » 4 years ago, # ^ |   0 He sorts the vector of pairs in step 3.
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Oh, weird. You don't have to do that sorting step though. For finding a repeated substring of size k, you can just iterate over the n-k+1 substrings of size k. When you add the current substring to the hash table (which maps "hash" to "start index of first occurrence"), check to see if there isn't already an entry. If an entry already exists, determine whether the current substring overlaps with the first occurrence of that substring. If it does, then there exist two substrings that don't overlap of size k.See some quick code I wrote here: http://pastebin.com/A3deJSZ0
•  » » » » » » » 4 years ago, # ^ |   0 I think sorting / hashtables are just personal preferences. I would use c++ set if I have to implement it. It gives O(nlg^2n) time complexity.
•  » » 5 weeks ago, # ^ |   0 There is no need for sorting I guess. If we encounter the same hash value just check whether the starting index of our current substring is greater than the mp[hash]+k-1 where k is the length of the substring.codeThis approach is O(n*log(n)).Can you give a test case where this might fail?I am following a similar approach for a simpler problem where the substring can overlapproblemmy effort code