# An Efficient Algorithm for LCS Problem between Two Arbitrary Sequences

Authors: Yubo Li
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The longest common subsequence (LCS) problem is a classic computer science problem. For the essential problem of computing LCS between two arbitrary sequencess1 and s2, this paper proposes an algorithm taking O(n+r) space and O(r+n2) time, where r is the total number of elements in the set (i,j)|s1[i]=s2[j]. The algorithm can be more efficient than relevant classical algorithms in specific ranges of r.


---

## Body

## 1. Introduction

The longest common subsequence (LCS) problem is a classic computer science problem and still attracts continuous attention [1–4]. It is the basis of data comparison programs and widely used by revision control systems for reconciling multiple changes made to a revision-controlled collection of files. It also has applications in bioinformatics and many other problems such as [5–7]. For the general case of an arbitrary number of input sequences, the problem is NP-hard [8]. When the number of sequences is constant, the problem is solvable in polynomial time [9]. For the essential problem ofcomputing LCS between two arbitrary sequences (LCS2), the complexity is at least proportional to the product of the lengths of sequences according to the conclusion as follows.It is shown that unless a bound onthe total number of distinct symbols[author’s note: the size of alphabet] is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings [9].The sizes of lengths of sequences make the quadratic time algorithms impractical in many applications. Hence, it is significant to design more efficient algorithm in practice. This paper is confined toLCS2 and is to present an algorithm that can be more efficient than relevant classical algorithms in specific scenarios.The following introduction is also confined to the case of two input sequences. Chvátal and Sankoff (1975) proposed a Dynamic Programming (DP) algorithm ofO(n2) space and time [10]. It is the basis of the algorithms for LCS problem. Soon in the same year, D.S. Hirschberg (1975) posted a Divide and Conquer (DC) algorithm that is a variation of the DP algorithm taking O(n) space and O(n2logn) time [11]. In 2000, Bergroth, Hakonen, and Raita contributed a survey [12] that shows in the past decades there is no theoretically improved algorithm based on Hirschberg’s DC algorithm [11] as it is so brilliant. In 1977, Hirschberg additionally proposed an O(pn+nlogn) algorithm and an O(p(m+1-p)logn) algorithm where p is length of LCS [13]. The first one is efficient when p is small, while the other one is efficient when p is close to m. Both of the two algorithms are more suitable when the length of LCS can be estimated beforehand. Then, Nakatsu, Kambayashi, and Yajima (1982) in [14] presented an algorithm suitable for similar sequences and having bound of O(n(m-p+1)) and O(m(m-p+1)logn). Let the two sequences be s1 and s2. Same in 1977, Hunt and Szymanski proposed an algorithm taking O(r) space and O((r+n)logn) time, where r is the total number of elements in the set (i,j)|s1[i]=s2[j] [15]. The algorithm reduces LCS2 to longest increasing subsequence (LIS) problem. Apostolico and Guerra (1987) in [16] proposed an algorithm based on [15] taking time O(nlogs+dloglogn), where d is the number ofdominant matches (as defined by Hirschberg [13]) and s is minimum of n and the alphabet size. Further, based on [16], Eppstein (1992) in [17] proposed an O(nlogs+dloglogmin(d,nm/d)) algorithm when the problem is sparse. If the alphabet size is constant, Masek and Paterson (1980) in [18] proposed an O(n2/log2n) algorithm utilizing themethod of four Russians(1970) [19]; Abboud, Backurs, and Williams (2015) in [20] showed an O(n2-ε) algorithm where ε>0. O(n2(loglogn)/log2n) algorithms are also proposed by Bille and Farach-Colton (2008) in [21] and Grabowski (2014) in [22], each of which has its own prerequisite. Restrained by the conclusion of [9, 20], in these decades an extensive amount of research keeps trying to achieve lower complexity than O(n2) of computing LCS between two condition-specific sequences for different applications, which also can be found in the survey [12]. For computing the length of LCS between two sequences over constant alphabet size, Allison and Dix (1986) presented an algorithm of O(n2/w), where w is the word-length of computer [23]. This algorithm uses bit-vector formula with 6 bit-wise operations. Although falling into the same complexity class as simple O(n2) DP algorithms, this algorithm is faster in practice. Crochemore, Iliopoulos, Pinzon, and Reid (2001) in [24] proposed a similar approach whose complexity is also O(n2/w). Due to the fact that only 4 bit-wise operations are used by the bit-vector formula, this approach gives a practical speedup over Allison and Dix’s algorithm.Compared with Chvátal-Sankoff algorithm [10], Hirschberg algorithm [11], and Hunt-Szymanski algorithm [15], most of the other algorithms for LCS problem between two sequences have more dependency, such as the following: the length of LCS is estimable beforehand [13, 14], two input sequences are similar [14, 16], problem is sparse enough [17], or the alphabet size is finite [16, 18, 20]. Some algorithms give speedup over classical algorithms in engineering [23, 24]. In this paper, an algorithm of O(n+r) space and O(r+n2) time is proposed for LCS2, where r is the total number of elements in the set (i,j)|s1[i]=s2[j] assuming the two arbitrary sequences are s1 and s2. The algorithm also reduces LCS2 to longest increasing subsequence (LIS) problem. Compared with relevant classical algorithms, the algorithm can be more efficient in specific range of r.This paper is organized as follows. In Section1, the current state of algorithms for LCS problem between two sequences including LCS2 is introduced. The proposed algorithm of this paper is presented and exemplified in Section 2, where preliminary terminologies needed to understand most of the paper and the theoretical basis of the proposed algorithm are also given. In Section 3, efficiency of the proposed algorithm is analyzed.


## 2. Algorithm

The longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences. This subsequence is not necessarily unique or not required to occupy consecutive positions within the original sequences (e.g., fafa is a longest common subsequence between nfafa and fanfa). LCS(seq1,seq2) is a defined function that returns a set containing all the LCSes between two sequences, while the longest increasing subsequence (LIS) is a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique (e.g., {1,2,3} is a longest increasing subsequence of {1,4,2,3}). LIS(seq) is also a defined function that returns a set containing all the LISs of a sequence. Assume s1=xnfafa and s2=yfanfa. For all s1[i]=s2[j], assume there is a sequence l, of which the elements are vectors in the form of (i,j) (see Figure 1). The left part of an element of l (l[u][0]) is the position of a symbol in s1, and the right part of the element (l[u][1]) is the position of the symbol in s2. l is sorted according to l[u][0] as the first key in ascending order and according to l[u][1] as the second key in descending order. Define (iu,ju),(iv,jv)∈l,(iu<iv)∧(ju<jv)⇐(iu,ju)<(iv,jv). Associating LIS(l) with LCS(s1,s2), it is bijective mapping between LIS(l) and LCS(s1,s2). Hence, LCSs1,s2can be reduced toLISl [25].According to the theoretical basis, Algorithm 1 is proposed for LCS2. The algorithm is designed to reduce LCS2 to LIS problem.Algorithm 1:Algorithm proposed in this paper.
1. ALG(s1,s2)  ▹   n=s2 2.▹   Step1:Constructnewdata 3.s1,s2→l  ▹   r=l 4. ▹   Step2:Themainprocedure 5.s2′0…n← (0, -) 6.pre0…r-1← - 7.end← 8.for  i=0  to  r-1  do 9.s2′ξ+11←i  ▹   ξ=li1 10.s2′[ξ+1][0]←s2′[ξ][0]+1 11.pre[i]←s2′ξ1 12.end←recordss2′ξ+1 13.for  j=ξ+2  to  r-1  do 14.if  s2′[j][0]<s2′ξ+10 15.s2′[j]←s2′ξ+1 16.else 17.break 18.▹   Step3:ComputeLISofl 19.l,pre,end→lis  ▹   lis∈LIS(l) 20. ▹   Step4:ComputeLCSbetweens1ands2 21.s1ors2,lis→lcs  ▹   lcs∈LCS(s1,s2) 22.return  lcsFigure 1
s 1, s2 and the conceived new data l.


### 2.1. Example

Reuses1=xnfafa,s2=yfanfa that are given previously. The process of computing LCSes between s1 and s2 using Algorithm 1 is illustrated in Figure 2 and presented as follows.Figure 2
Example.
(a)
Two sequences:s1 and s2 (b)
New datal constructed from s1 and s2 (c)
Write operation ins2′ (d)
Final result ofpre and endScanl from left to right. The right part of l[0]=(1,3) is 3, 3+1=4; then s2′[4] is going to be computed. s2′[4][0]=s2′[3][0]+1=1; s2′[4][1] is the position of (1,3) in l; therefore s2′[4]=(1,0).The right part ofs2′[4] is 0; then pre[0]=s2′[3][1].e n d records the information of s2′[4]=(1,0).Then,s2′[5][0]<s2′[4][0]; therefore s2′[5]=s2′[4]; s2′[6][0]<s2′[4][0]; therefore s2′[6]=s2′[4].Forl[1]=(2,4), the right part of (2,4) is 4; then s2′[5] is going to be computed. s2′50=s2′40+1=2; s2′[5][1] is the position of (2,4) in l; therefore s2′[5]=(2,1).The right part ofs2′[5] is 1; then pre[1]=s2′[4][1].e n d records the information of s2′[5]=(2,1).Then,s2′[6][0]<s2′[5][0]; therefore s2′[6]=s2′[5].Forl[2]=(2,1), s2′[2][0]=s2′[1][0]+1=1; s2′[2][1] is the position of (2,1) in l; therefore s2′[2]=(1,2).The right part ofs2′[2] is 2; then pre[2]=s2′[0][1].e n d records the information of s2′[2]=(1,2).Then,s2′[3][0]<s2′[2][0]; therefore s2′[3]=s2′[2]. s2′[4][0]≮s2′[2][0], s2′[4] is kept unchanged, and the rest of the elements  s2′[5]  and  s2′[6]  are not going to be checked.The rest of the elements ofl can be computed in the same way. Figure 2(d) is the final result of pre and end.From the auxiliary dataend, it can be seen that there is only one LIS in l. The length of the LIS is 4.e n d [ 3 ] points to 7; therefore the last element of the LIS is l[7]=(5,5).p r e [ 7 ] = 5 and l[5]=(4,4); then the last two elements of the LIS are (4,4)(5,5).p r e [ 5 ] = 4 and l[4]=(3,2); then (3,2)(4,4)(5,5).p r e [ 4 ] = 2 and l[2]=(2,1); then (2,1)(3,2)(4,4)(5,5).p r e [ 2 ] is null. Then the LIS is (2,1)(3,2)(4,4)(5,5).Since it is bijective mapping betweenLIS(l) and LCS(s1,s2), (2,1)(3,2)(4,4)(5,5)∈LIS(l)⇒s1[2]s1[3]s1[4]s1[5]=s2[1]s2[2]s2[4]s2[5]=fafa∈LCS(s1,s2). fafa is the only LCS between s1 and s2.


### 2.2. Complexity

According to the conclusion of [15] (paragraph 3 page 4), we have the following.Step 1 [author’s note: similar to step 1 of Algorithm1 of this paper] can be implemented by sorting each sequence while keeping track of each element’s original position. We may then merge the sorted sequences creating the MACHLISTs [author’s note: similar to array l of this paper] as we go. This step takes a total of O(nlogn) time and O(n) space.Assumer is the number of match vectors between s1 and s2. Step 1 of Algorithm 1 is a process of O(n+r) space and O(max(r,nlogn)) time. As the length of LCS is O(n), step 3 is a process of O(r) space and O(n) time. Step 4 takes O(n) space and O(n) time. Write operations in s2′ for all element of l are listed together in Figure 2(c). In pre and end (see Figure 2(d)), the time of write operation is r. In s2′, the time of write operation of dark gray block is r; the time of write operation of light gray block is at most ∑i=1n-1i=n(n-1)/2=n2-n/2, which is illustrated in Figure 3. Therefore, step 2 takes O(n+r) space and Or+n2-n/2 time. Complexities of every step of Algorithm 1 are listed in Table 1. The whole algorithm takes O(n+r) space and Or+n2-n/2=O(r+n2) time, which is dominated by step 2.Table 1
Complexity of each procedure of Algorithm1.
Procedure of algorithm Space Time Step 1 O ( n + r ) O ( m a x ( r , n  l o g  n ) ) Step 2 O n + r O r + n 2 - n 2 Step 3 O r O n Step 4 O n O nFigure 3
Maximum write operation of light gray block ins2′ of Alggorithm 1.


## 2.1. Example

Reuses1=xnfafa,s2=yfanfa that are given previously. The process of computing LCSes between s1 and s2 using Algorithm 1 is illustrated in Figure 2 and presented as follows.Figure 2
Example.
(a)
Two sequences:s1 and s2 (b)
New datal constructed from s1 and s2 (c)
Write operation ins2′ (d)
Final result ofpre and endScanl from left to right. The right part of l[0]=(1,3) is 3, 3+1=4; then s2′[4] is going to be computed. s2′[4][0]=s2′[3][0]+1=1; s2′[4][1] is the position of (1,3) in l; therefore s2′[4]=(1,0).The right part ofs2′[4] is 0; then pre[0]=s2′[3][1].e n d records the information of s2′[4]=(1,0).Then,s2′[5][0]<s2′[4][0]; therefore s2′[5]=s2′[4]; s2′[6][0]<s2′[4][0]; therefore s2′[6]=s2′[4].Forl[1]=(2,4), the right part of (2,4) is 4; then s2′[5] is going to be computed. s2′50=s2′40+1=2; s2′[5][1] is the position of (2,4) in l; therefore s2′[5]=(2,1).The right part ofs2′[5] is 1; then pre[1]=s2′[4][1].e n d records the information of s2′[5]=(2,1).Then,s2′[6][0]<s2′[5][0]; therefore s2′[6]=s2′[5].Forl[2]=(2,1), s2′[2][0]=s2′[1][0]+1=1; s2′[2][1] is the position of (2,1) in l; therefore s2′[2]=(1,2).The right part ofs2′[2] is 2; then pre[2]=s2′[0][1].e n d records the information of s2′[2]=(1,2).Then,s2′[3][0]<s2′[2][0]; therefore s2′[3]=s2′[2]. s2′[4][0]≮s2′[2][0], s2′[4] is kept unchanged, and the rest of the elements  s2′[5]  and  s2′[6]  are not going to be checked.The rest of the elements ofl can be computed in the same way. Figure 2(d) is the final result of pre and end.From the auxiliary dataend, it can be seen that there is only one LIS in l. The length of the LIS is 4.e n d [ 3 ] points to 7; therefore the last element of the LIS is l[7]=(5,5).p r e [ 7 ] = 5 and l[5]=(4,4); then the last two elements of the LIS are (4,4)(5,5).p r e [ 5 ] = 4 and l[4]=(3,2); then (3,2)(4,4)(5,5).p r e [ 4 ] = 2 and l[2]=(2,1); then (2,1)(3,2)(4,4)(5,5).p r e [ 2 ] is null. Then the LIS is (2,1)(3,2)(4,4)(5,5).Since it is bijective mapping betweenLIS(l) and LCS(s1,s2), (2,1)(3,2)(4,4)(5,5)∈LIS(l)⇒s1[2]s1[3]s1[4]s1[5]=s2[1]s2[2]s2[4]s2[5]=fafa∈LCS(s1,s2). fafa is the only LCS between s1 and s2.


## 2.2. Complexity

According to the conclusion of [15] (paragraph 3 page 4), we have the following.Step 1 [author’s note: similar to step 1 of Algorithm1 of this paper] can be implemented by sorting each sequence while keeping track of each element’s original position. We may then merge the sorted sequences creating the MACHLISTs [author’s note: similar to array l of this paper] as we go. This step takes a total of O(nlogn) time and O(n) space.Assumer is the number of match vectors between s1 and s2. Step 1 of Algorithm 1 is a process of O(n+r) space and O(max(r,nlogn)) time. As the length of LCS is O(n), step 3 is a process of O(r) space and O(n) time. Step 4 takes O(n) space and O(n) time. Write operations in s2′ for all element of l are listed together in Figure 2(c). In pre and end (see Figure 2(d)), the time of write operation is r. In s2′, the time of write operation of dark gray block is r; the time of write operation of light gray block is at most ∑i=1n-1i=n(n-1)/2=n2-n/2, which is illustrated in Figure 3. Therefore, step 2 takes O(n+r) space and Or+n2-n/2 time. Complexities of every step of Algorithm 1 are listed in Table 1. The whole algorithm takes O(n+r) space and Or+n2-n/2=O(r+n2) time, which is dominated by step 2.Table 1
Complexity of each procedure of Algorithm1.
Procedure of algorithm Space Time Step 1 O ( n + r ) O ( m a x ( r , n  l o g  n ) ) Step 2 O n + r O r + n 2 - n 2 Step 3 O r O n Step 4 O n O nFigure 3
Maximum write operation of light gray block ins2′ of Alggorithm 1.


## 3. Efficiency

The algorithm proposed in this paper is designed to compute LCS between two arbitrary sequences, which is the same as the original intention of the classical algorithms: Chvátal-Sankoff algorithm [10], Hirschberg algorithm [11], and Hunt-Szymanski algorithm [15]. The proposed algorithm can be more efficient in specific range of r compared with the classical algorithms, where r is the total number of elements in the set (i,j)|s1[i]=s2[j] assuming two arbitrary sequences are s1 and s2.


### 3.1. Comparison with Hunt-Szymanski Algorithm

As the original position ins2 of each element of l is not used in the process of computing, in Figure 4 Hunt-Szymanski algorithm needs to utilize binary search to locate the position in s2′ for write operation for each element of l. The time of binary search in s2′ of Hunt-Szymanski algorithm is at most ∑i=1nlogi+(r-n)logn, which is illustrated in Figure 5. UsingStirling’s approximation [26–28], ∑i=1nlogi+(r-n)logn=log∏i=1ni+(r-n)logn=log(n!)+(r-n)logn≈nlogn+(r-n)logn=rlogn. If the demand is only returning one LCS or the length of LCS, array l of the algorithm proposed in this paper can be replaced with the MATCHLIST that is used in Hunt-Szymanski algorithm. Therefore, the algorithm proposed in this paper can take O(n) space that is the same as the one Hunt-Szymanski algorithm takes. The main difference between them is the time consumed in s2′. In Figure 3, the total time of write operation of both dark gray and light gray blocks is at most r+n2-n/2. As 0⩽r⩽n2, if r+n2-n/2<rlogn⇒n2-n/2(logn-1)<r⩽n2, the algorithm proposed in this paper is more efficient in time than Hunt-Szymanski algorithm (see Figure 7).Figure 4
Write operation ins2′ of Hunt-Szymanski algorithm.Figure 5
Maximum time of binary search of Hunt-Szymanski algorithm.


### 3.2. Comparison with Chvátal-Sankoff Algorithm

Chvátal-Sankoff algorithm needsn2 times of comparison in n2 space, which is illustrated in Figure 6. To simplify the analysis, only the r+n2-n/2 time consumed in s2′ of the algorithm proposed in this paper is going to be compared with the n2 time of Chvátal-Sankoff algorithm. As 0⩽r⩽n2, if r+n2-n/2<n2⇒0⩽r<n2+n/2, the algorithm proposed in this paper is more efficient in time than Chvátal-Sankoff algorithm (see Figure 7). In this case of r, the proposed algorithm is also more efficient in space than Chvátal-Sankoff algorithm.Figure 6
Time of comparison of Chvátal-Sankoff algorithm.Figure 7
Comparison of efficiency against classical algorithms.


### 3.3. Comparison with Hirschberg Algorithm

Hirschberg algorithm takesO(n) space and O(n2logn) time. As 0⩽r⩽n2, the algorithm proposed in this paper takes O(n+r) space and O(r+n2-n/2)=O(n2) time. Therefore, the proposed algorithm has lower time complexity than Hirschberg algorithm.


## 3.1. Comparison with Hunt-Szymanski Algorithm

As the original position ins2 of each element of l is not used in the process of computing, in Figure 4 Hunt-Szymanski algorithm needs to utilize binary search to locate the position in s2′ for write operation for each element of l. The time of binary search in s2′ of Hunt-Szymanski algorithm is at most ∑i=1nlogi+(r-n)logn, which is illustrated in Figure 5. UsingStirling’s approximation [26–28], ∑i=1nlogi+(r-n)logn=log∏i=1ni+(r-n)logn=log(n!)+(r-n)logn≈nlogn+(r-n)logn=rlogn. If the demand is only returning one LCS or the length of LCS, array l of the algorithm proposed in this paper can be replaced with the MATCHLIST that is used in Hunt-Szymanski algorithm. Therefore, the algorithm proposed in this paper can take O(n) space that is the same as the one Hunt-Szymanski algorithm takes. The main difference between them is the time consumed in s2′. In Figure 3, the total time of write operation of both dark gray and light gray blocks is at most r+n2-n/2. As 0⩽r⩽n2, if r+n2-n/2<rlogn⇒n2-n/2(logn-1)<r⩽n2, the algorithm proposed in this paper is more efficient in time than Hunt-Szymanski algorithm (see Figure 7).Figure 4
Write operation ins2′ of Hunt-Szymanski algorithm.Figure 5
Maximum time of binary search of Hunt-Szymanski algorithm.


## 3.2. Comparison with Chvátal-Sankoff Algorithm

Chvátal-Sankoff algorithm needsn2 times of comparison in n2 space, which is illustrated in Figure 6. To simplify the analysis, only the r+n2-n/2 time consumed in s2′ of the algorithm proposed in this paper is going to be compared with the n2 time of Chvátal-Sankoff algorithm. As 0⩽r⩽n2, if r+n2-n/2<n2⇒0⩽r<n2+n/2, the algorithm proposed in this paper is more efficient in time than Chvátal-Sankoff algorithm (see Figure 7). In this case of r, the proposed algorithm is also more efficient in space than Chvátal-Sankoff algorithm.Figure 6
Time of comparison of Chvátal-Sankoff algorithm.Figure 7
Comparison of efficiency against classical algorithms.


## 3.3. Comparison with Hirschberg Algorithm

Hirschberg algorithm takesO(n) space and O(n2logn) time. As 0⩽r⩽n2, the algorithm proposed in this paper takes O(n+r) space and O(r+n2-n/2)=O(n2) time. Therefore, the proposed algorithm has lower time complexity than Hirschberg algorithm.



---

*Source: 4158071-2018-11-29.xml*