About LCS in O(nlogn)

Riyad · Post by **Riyad** » Thu Apr 29, 2004 9:34 pm

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.........

Riyad

Duy Hung · Post by **Duy Hung** » Sat May 08, 2004 3:42 pm

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 · Post by **UFP2161** » Sat May 08, 2004 4:52 pm

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 · Post by **Miguel Angel** » Sat May 08, 2004 8:53 pm

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

.

artem · Post by **artem** » Tue Dec 20, 2005 9:03 pm

In worst case its works N*N*logN

OJ Board

About LCS in O(nlogn)

About LCS in O(nlogn)

Egal..