LCS again...help

yogeshgo05 · Post by **yogeshgo05** » Wed Jul 26, 2006 7:07 am

hi guys..

could any body tell me about how generate all possible LCS b/w two strings ..i hav tried backtrack sol which didnt work ..probably wasted around 3 days trying to find the alll possible lcs b/w string ...
(Firstly is it possible without trying all possible brute approach..i think not..)(i searched web ,stevenhalim's site ,TC..but not conclusive..)
i just want an idea to proceed..plz help

thanks

Moha · Post by **Moha** » Wed Jul 26, 2006 7:14 am

Please pay attention that, this is a output oriented order. for an instance LCS(a^n,a^n). so this is a exponential output. You can speed up your code with a dynamic table. but counting them has a polynomial order.

yogeshgo05 · Post by **yogeshgo05** » Wed Jul 26, 2006 7:17 am

hi thanks ..
could u help me with a link on the web which deals with this case..

bugzpodder · Post by **bugzpodder** » Mon Jul 31, 2006 7:20 am

essentially you backtrack through your matrix. Recall that LCS is defined as:

f(i,j)=max(f(i-1,j-1)+1, f(i-1,j), f(i,j-1)) if x==y[j]
=max(f(i-1,j),f(i,j-1)) if x!=y[j]

hence you want to find all possible paths from f(M,N) to f(0,0), with an edge between f(i,j) and f(i-a, j-b) if the max value of f(i-a,j-b) is used to get f(i,j) as above, |a|,|b|<=1

How do you find all possible shortest paths? DFS. keep the stack. since you have to output everything, you dont need to cache any result at all.

beloni · Post by **beloni** » Mon Jul 31, 2006 5:55 pm

hello, take a look at this link: http://www.comp.nus.edu.sg/~stevenha/pr ... ence_(LCS)

I hope it helps