An input sensitive online algorithm for LCS computation

Abstract. We consider the classic problem of computing (the length of) the longest common subsequence (LCS) between two strings A and B with lengths m and n, respectively. There are several input sensitive algorithms for this problem, such as the O(σn+min{Lm,L(n−L)}) algorithms by Rick [15] and Goeman and Clausen [5] and the O(σn + min{σd, Lm}) algorithms by Chin and Poon [4] and Rick [15]. Here L is the length of the LCS and d is the number of dominant matches between A and B, and σ is the alphabet size. These algorithms require O(σn) time preprocessing for both A and B. We propose a new fairly simple O(σm + min{Lm,L(n − L)}) time algorithm that works in online manner: It needs to preprocess only A, and it can process B one character at a time, without knowing the whole string B beforehand. The algorithm also adapts well to the linear space1 scheme of Hirschberg [6] for recovering the LCS, which was not as easy with the above-mentioned algorithms. In addition, our scheme fits well into the context of incremental string comparison [12,10]. The original algorithm of Landau et al. [12] for this problem uses O(σm + Lm) space. By using our scheme instead, the space usage becomes O(σm + min{Lm,L(n − L)})