About LCS in O(nlogn)

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

About LCS in O(nlogn)

Post by Riyad »

is it possible to find an algorithm to find LCS in O(nlogn) ??????? i know a solution that runs in O(n^2)..........if any one know an algorithm of LCS in O(nlogn) plizzzzzzzzzzzz let me know ....... as far as i know there is no algorithm for LCS that runs in O(nlogn)...................

but i know there is a O(nlogn)solution for LIS ............... can any one give the alogrithm to me ,,,,, any links or pseudo code is appreciable ................... plizzzzzzzzzz help me in this .....

Regards.........:roll:
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
Duy Hung
New poster
Posts: 7
Joined: Sat Jan 17, 2004 3:50 pm
Location: Viet Nam
Contact:

Post by Duy Hung »

yes, i am sure to say that there is no solution for solving the LCS problem in O(nlogn)....but everything can be wrong. so, if only anyone could tell me whether I was right or wrong... thx so much
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Not O (n log n), but it can be solved in O (r log n), where r is the sum of r(i) where r(i) is the number of times that the ith character of the first string appears in the second string.

Reference: Algorithms on Strings, Trees, and Sequences, pp. 290-291.
Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Egal..

Post by Miguel Angel »

Which is proportional to NlogN, in such case will be smth like O(M log N), given the two length of the strings. Anyway, that's not the case, there's a way to do it, based on balanced trees (on arrays) where you can perform operations in log N speed. The first word will be a set of finite characters (or you can make it finite) ordered, and that will be your tree, while the other word, following the order it has making querys and updates to such tree :).
:D Miguel & Marina :D
artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem »

In worst case its works N*N*logN
Post Reply

Return to “Algorithms”