OJ Board

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

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

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.

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 .

In worst case its works N*N*logN