LCS again...help

Let's talk about algorithms!

Moderator: Board moderators

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

LCS again...help

Post by yogeshgo05 »

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:

Post by Moha »

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

Post by yogeshgo05 »

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

Post by bugzpodder »

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

Post by beloni »

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

Post Reply

Return to “Algorithms”