k790alex's blog

By k790alex, 5 years ago, In English,

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.

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

easy, if you know suffix automaton. just calculate first and last position in string for all states.

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

    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   Vote: I like it +1 Vote: I do not like it

      yes, the same

      upd 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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you explain solution for k non-overlaping substrings?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 5   Vote: I like it 0 Vote: I do not like it

          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<LEN we need to pop it out and modificate both sets. after that, check for size if at least K. it looks O(Nlog2N).

          + even easier: need only sorted array of every segment, and greedy will works: first index i, lower_bound(i+LEN) and so on K times.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it -8 Vote: I do not like it

            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   Vote: I like it 0 Vote: I do not like it

          i explained, please check for mistakes:)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hash maybe help

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

    how?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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).

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

What test cases does your approach fail on?

Edit: it fails for "aaaaa" (it returns "a")

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  1. 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.

  2. Keep one extra information with each hash that is starting index of this string in the given string.

  3. 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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What sorting step?

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

          He sorts the vector of pairs in step 3.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    code

    This 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 overlap

    problem

    my effort code