Abstract: This paper discusses the problem of determining the longest common subsequence (LCS) of two sequences. Here we view this problem in the background of the well known algorithm for the longest increasing subsequence (LIS). This new approach leads us to a new online algorithm which runs in time and in space where is the length of the input sequences and is the number of minimal matches between them. Using an advanced technique of van Emde Boas trees the time complexity bound can be reduced to preserving the space bound of .

Keywords: longest common subsequence, longest increasing subsequence, online algorithm.

ACM Classification Keywords:G.2.1 Discrete mathematics: Combinatorics

Link:

A NEW ALGORITM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM

Vahagn Minasyan

http://www.foibg.com/ijita/vol17/ijita17-3-p03.pdf