  In this paper, we revisit the much studied LCS problem for two given
sequences. Based on the algorithm of Iliopoulos and Rahman for solving the LCS
problem, we have suggested 3 new improved algorithms. We first reformulate the
problem in a very succinct form. The problem LCS is abstracted to an abstract
data type DS on an ordered positive integer set with a special operation
Update(S,x). For the two input sequences X and Y of equal length n, the first
improved algorithm uses a van Emde Boas tree for DS and its time and space
complexities are O(R\log\log n+n) and O(R), where R is the number of matched
pairs of the two input sequences. The second algorithm uses a balanced binary
search tree for DS and its time and space complexities are O(R\log L+n) and
O(R), where L is the length of the longest common subsequence of X and Y. The
third algorithm uses an ordered vector for DS and its time and space
complexities are O(nL) and O(R).
