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

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | Errichto | 187 |

4 | rng_58 | 186 |

5 | SecondThread | 183 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 21:38:22 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

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

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

"These lists should be sorted in decreasing order".

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

I thing this is a wrong on typing ! :)

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

Helpful post!

Could you please provide me the code, It would be very helpful. Thank you

Forming the final array would take N*M complexity i think.

nice idea