### farnabaz's blog

By farnabaz, 7 years ago, ,

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??

• 0

 » 7 years ago, # | ← Rev. 2 →   0 I think there is no NLogN algorithm. Can you describe your solution or publish your code?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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 Sequences by Dan Gusfield
•  » » 7 years ago, # ^ |   0 The algorithm is based on converting LCS to LIS ,for conversion we do as followfirst 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 a didn't occurs in B , second character of A is b the 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 A a= {} b={4 ,3 ,1} a={} b={4 ,3 ,1} a= {} b={4 ,3 ,1} a={} b={4 ,3 ,1}now 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,1now the LIS in A' is LCS of A and B
•  » » » 7 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » 7 years ago, # ^ |   0 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 !
•  » » » » 7 years ago, # ^ |   0 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#891898However this solution only works when at most one sequence has repetitions.
•  » » » » » 7 years ago, # ^ |   0 The solution work when we calculate the Longest strictly Increasing subsequence
•  » » » » 7 years ago, # ^ |   0 counter example: azabbgfhtuazargfhaza ppazassgfhjkgfhazasxvaza
•  » » » » » 7 years ago, # ^ |   0 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. int lcsLength(char X[],char Y[]){ int m=X.length; int n=Y.length; int T[][]=new int[m+1][n+1]; for(int i=0;i<=m;i++) T[i][0]=0; for(int i=0;i<=n;i++) T[0][i]=0; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(X[i-1]==Y[j-1]) T[i][j]=T[i-1][j-1]+1; else T[i][j]=Math.max(T[i-1][j],T[i][j-1]); } } return T[m][n]; }
•  » » » » » 7 years ago, # ^ |   0 now lets run the algorithm on your counter example : if A=azabbgfhtuazargfhaza and B=ppazassgfhjkgfhazasxvaza then we shoul have a -> { 24, 22, 18, 16, 5, 3 } z -> { 23, 17, 4 } a -> { 24, 22, 18, 16, 5, 3 } b -> { } b -> { } g -> { 13, 8 } f -> { 14, 9 } h -> { 15, 10 } t -> { } u -> { } a -> { 24, 22, 18, 16, 5, 3 } z -> { 23, 17, 4 } a -> { 24, 22, 18, 16, 5, 3 } r -> { } g -> { 13, 8 } f -> { 14, 9 } h -> { 15, 10 } a -> { 24, 22, 18, 16, 5, 3 } z -> { 23, 17, 4 } a -> { 24, 22, 18, 16, 5, 3 } A'= { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 } { } { } { 13, 8 } { 14, 9 } { 15, 10 } { } { } { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 } { } { 13, 8 } { 14, 9 } { 15, 10 } { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 } A'=24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 13, 8, 14, 9, 15, 10, 24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 13, 8, 14, 9, 15, 10, 24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 12now 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!
•  » » » » » » 7 years ago, # ^ |   0 How would A' look like if A = aa...a(50000 times)?
•  » » » » » » » 7 years ago, # ^ |   0 A=B=aa...(50000 times) is the worst case for this algorithm with O(n^2logn) running time and O(n^2) memory usage
•  » » » 7 years ago, # ^ |   0 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.
 » 4 days ago, # |   0 if some get AC in the question then please post the soltuion