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 »

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 »

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 »

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 »

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 »

I'm talking about subsequence.

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

Post by misof »

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 »

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”