help with research paper on LCS

Revision en1, by t3rminated, 2017-01-16 18:19:44

I was reading about algorithms to find LCS in O(nlogn) and i came through this research paper — link

It claims to find LCS in O((n+r)logn) where r are the number of matching pairs.

But I can't understand how the final algorithm is O(n+rlogn) , I guess the algorithm is O(n*r*logn) ,please clear my doubt I can't understand?

Tags longest, common, subsequence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English t3rminated 2017-01-16 18:35:04 242
en2 English t3rminated 2017-01-16 18:31:25 947
en1 English t3rminated 2017-01-16 18:19:44 634 Initial revision (published)