Блог пользователя swordx

Автор swordx, история, 5 лет назад, По-английски

Hello Guys,

Can you share your thoughts on the following question:

Given a string, we have to find the longest non-overlapping repeating subsequence. For example, If we have a string like "abdead", then here the answer is "ad" because longest repeating subsequence is "ad" which is non-overlapping.

My initial thought on this question is that we can use the concept of longest common subsequence but we need to manage the non-overlapping part.

Thanks in advance!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Split the string into two strings $$$s_1,s_2$$$ such that $$$s=s_1s_2$$$ in all possible ways (there are $$$n-1$$$ ways) and then find the LCS of those two strings. The largest such LCS is the solution. The complexity is $$$O(n^3)$$$. It can probably be done faster though.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    You can use ternary search for the split, and it'll be $$$O(n^2log(n))$$$

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      You cannot use ternary search. For example for s = "sxyaatxysaaxyt" the LCSs for subsequent splits are 1 2 3 3 4 5 4 5 4 3 3 2 1.

      However, there is $$$O(n^2)$$$ algorithm for finding the optimal split.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if s = "abcadbcd" then longest non onverlapping repeating subsequence is abcd, but with your approach there donot exist a spliting of s in which LCS of s1 and s2 is abcd. please correct me if i am wrong

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, you need to find the longest subsequence which has the form $$$ss$$$ for some string $$$s$$$, not two identical non-overlapping subsequences.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For each suffix run z-algorithm. O(n^2) update: only works for segments