The Best LCS!

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

The Best LCS!

Post by Emilio » Thu Mar 30, 2006 4:04 am

Hello there!
I want to know what is the best order to find what is the LCS of two strings.
Memory order and time order.
If anyone know the answer he/she will be grateful if he/she reply.
Thanks in advance :D

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

Post by nukeu666 » Thu Mar 30, 2006 4:40 pm

isnt the best way to find longest common substring with dymanic programming?
google

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Apr 02, 2006 2:51 am

Yeah, but I want to know what is the best order both time and memory, and if possible what are their corresponding algorithms.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Apr 02, 2006 10:13 am

And are you talking about the longest common substring or subsequence?

The difference is that the substring has to be continuous in both strings. For "abucv" and "xabyzc" the longest common substring is "ab", subsequence is "abc".

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Apr 02, 2006 4:21 pm

I'm talking about subsequence.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Apr 05, 2006 7:17 pm

http://www.ics.uci.edu/~eppstein/161/960229.html
probably more than you will ever need, and explained nicely :)

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Apr 06, 2006 8:41 am

Thanks misof! :)
I only have had a short time to have a simple look, but it really seems complete and explained nicely

Post Reply

Return to “Algorithms”