Damon's blog

A question about Longest Common Subsequence (LCS) !?
By Damon, 11 years ago, In English

Hi :) We have two string with same size ! ( n = strings.size() )

I want an algorithm with O(n.lg n) , to find LCS of this strings .

What is best Order of this problem ? I can find it with O(n^2) by using dp !

sry 4 my bad English! :|

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

Comments Comments (9)
| Write comment?
»
11 years ago, # |
  Vote: I like it -16 Vote: I do not like it

How much do you pay for nlogn? and for linear?

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Well, you can decrease it to a LIS problem. Lets say you have strings S1 and S2. You can take S1 and for every character put in a list for that character the indexes where the character occurs. These lists should be sorted in decreasing order. For example if you have string "abacba" you have these lists

  • 'a': 5,2,0
  • 'b': 1,4
  • 'c': 3

Now, if you look at S2 and for each character put in a sequence its list(note that it can be empty), you have a sequence in which you should search for LIS. Here's with the example if S2 is 'baaxac' you have sequence 1,4, 5,2,0, 5,2,0, ,5,2,0, 3. The LIS of this sequence is 3 as the answer would be. If you have to retrieve some string as an answer you can just retrieve the corresponding letters. Now that we have a LIS problem, it can be solved in nlogn. If you don't know how, there is a very recent post about that here. The only problem is that the sequence can get big, but it is in rare situations, so you have an average case of nlogn and a worst case of O(NM) or something like that, but it is still a good idea, which is worth the thoughts, especially if you have some restrictions about the type of the input

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

    Thanks a lot :) I want this too , ty for help :)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    "These lists should be sorted in decreasing order".

    So shouldn't the list for b read [4, 1] rather than [1, 4] ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I thing this is a wrong on typing ! :)

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes, it is! Thank you! :). The answer is still 3 though..

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Helpful post!

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

    nice idea

    → Reply
»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I think there is a way to solve LCS in O(N*log(N)) using Suffix Array algorithm

you can read more on cp-algo

similar problem: https://www.spoj.com/problems/LCS/

→ Reply