## LCS again...help

Moderator: Board moderators

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

### LCS again...help

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm
hi thanks ..
could u help me with a link on the web which deals with this case..

bugzpodder
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(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
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
hello, take a look at this link: http://www.comp.nus.edu.sg/~stevenha/pr ... ence_(LCS)

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