I tried to solve LCS0 on SPOJ with O(r log n) algorithm, but i'm getting **TLE**, is there any linear algorithm for this problem??

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

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

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

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2020 02:44:30 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I think there is no NLogN algorithm. Can you describe your solution or publish your code?

O(RlogN) not O(NlogN), where R is a special parameter that can be bigger than MN, but in many cases it's small enough.

the algorithm is mentioned in

Algorithms on Strings, Trees and SequencesbyDan GusfieldThe algorithm is based on converting LCS to LIS ,for conversion we do as follow

first for each character c in A we make a list of index of occurrence of c in B in descending order for example if we have A=abababab and B=bcbb first character of A is a and

adidn't occurs in B , second character of A isbthe descending list of occurrence indexes is { 4,3,1} because b occurs in positions 1 and 3 and 4 , we should make this lists for each character of Anow we replace each character of A with new calculated list as follows and make A'

A'={}{4,3,1}{}{4,3,1}{}{4,3,1}{}{4,3,1}=4,3,1,4,3,1,4,3,1,4,3,1

now the LIS in A' is LCS of A and B

Algorithm described above must not get TLE it must get WA because algo is incorrect.There is no nlogn algo the fastest algo's complexity is O(n * ceil(m/log n)) (n >= m). Recurrence : dp[i][j] = max((a[i] == b[j]) * (dp[i — 1][j — 1] + 1), max(dp[i — 1][j], dp[j][i — 1])); We can notice that we need only two rows then we can store only array of size [3][50000]. Such solution must get AC.

The time complexity of the above algorithm is O(r logk) where r is a parameter that can vary and in worst case can be as bad as n*m and k is length of longest common subsequence of two string , so the worst case running time can be O(n*n*logn) but in many cases in real application r is small enough ,also the (theoretically) fastest algorithm for longest common subsequence runs in O(n log s + c log log min(c,mn/c)) developed by David Eppstein,and if you say that some algorithm is wrong you should show a counter example and if you can't go for proof !

It's not all incorrect. There is a reduction from LCS to LIS: http://apps.topcoder.com/forums/?module=Thread&threadID=594064&start=0&mc=21#891898

However this solution only works when at most one sequence has repetitions.

The solution work when we calculate the Longest strictly Increasing subsequence

counter example: azabbgfhtuazargfhaza ppazassgfhjkgfhazasxvaza

I'm not sure your are computing LCS correctly, the LCS of your counter example with the following code is

`12`

, same as my O(RlogN) algorithm, it's not a counter example for algorithm.now lets run the algorithm on your

counterexample :if A=azabbgfhtuazargfhaza and B=ppazassgfhjkgfhazasxvaza then we shoul have

now if you calculate the Length of Longest Strictly Increasing Subsequence of A' you get 12 same as a DP solution.i strongly suggest you to read the **Dan Gusfield ** book or if you don't like go for a better counter example and try your best!

How would A' look like if A = aa...a(50000 times)?

A=B=aa...(50000 times) is the worst case for this algorithm with O(n^2logn) running time and O(n^2) memory usage

The reduction from LCS to LIS works only when at least one sequence hasn't repetitions. This problem can be solved in O(NM) time complexity using O(max(N,M)) memory complexity.

if some get AC in the question then please post the soltuion