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

A question about Longest Common Subsequence (LCS) !?
Автор Damon, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
11 лет назад, # |
← 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

→ Ответить