### Damon's blog

By Damon, 8 years ago,

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! :|

• +1

 » 8 years ago, # |   -16 How much do you pay for nlogn? and for linear?
 » 8 years ago, # | ← Rev. 3 →   +8 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
•  » » 8 years ago, # ^ | ← Rev. 2 →   +2 Thanks a lot :) I want this too , ty for help :)
•  » » 8 years ago, # ^ |   +1 "These lists should be sorted in decreasing order".So shouldn't the list for b read [4, 1] rather than [1, 4] ?
•  » » » 8 years ago, # ^ |   +1 I thing this is a wrong on typing ! :)
•  » » » » 8 years ago, # ^ |   +1 Yes, it is! Thank you! :). The answer is still 3 though..
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Helpful post!
•  » » 8 months ago, # ^ |   -8 Could you please provide me the code, It would be very helpful. Thank you
•  » » 7 months ago, # ^ |   -10 Forming the final array would take N*M complexity i think.
•  » » 3 weeks ago, # ^ |   0 nice idea