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
LCS again...help
Moderator: Board moderators

 New poster
 Posts: 47
 Joined: Sun Nov 27, 2005 12:43 pm

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
essentially you backtrack through your matrix. Recall that LCS is defined as:
f(i,j)=max(f(i1,j1)+1, f(i1,j), f(i,j1)) if x==y[j]
=max(f(i1,j),f(i,j1)) 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(ia, jb) if the max value of f(ia,jb) 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.
f(i,j)=max(f(i1,j1)+1, f(i1,j), f(i,j1)) if x==y[j]
=max(f(i1,j),f(i,j1)) 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(ia, jb) if the max value of f(ia,jb) 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.
hello, take a look at this link: http://www.comp.nus.edu.sg/~stevenha/pr ... ence_(LCS)
I hope it helps
I hope it helps
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor