一个给定字符串的子序列是在该字符串序列中删除0个或者多个元素后得到的序列。给定序列X={x1,X2,…，Xn)和]，={y1,y2,…，yn}，设它们是定义在字符集∑={σ1,σ2,...，σs}上的两个字符串，最长公共子序列(简称LCS)问题就是找出关于X和Y的公共子序列中长度最长的子序列。　　 在求解LCS问题的众多算法中，由Rick提出的算法[15，16]有着良好的性能，该算法后来被Goeman和Clausen做了进一步的优化和改进[2]。改进后算法的空间复杂度为线性复杂度O(ns)。然而当该算法应用于大规模序列(如遗传基因序列)以及N-LCS问题的时候，空间依然会成为算法的瓶颈。如2001年4月UCUS人类基因组计划发布了人类基因序列，共包含28亿对碱基，相应的字符串序列为6G，如果用Goeman-Clausen LCS算法求解此问题时需要96G的存储空间，而96G的空间已经超出了普通计算机的内存空间。因此空间的优化成了实践中迫切需要解决的问题。　　 本文针对Goeman-Clausen LCS算法进行空间改进和优化，做了下面几点工作：(1)对Goeman-Clausen算法中的辅助数组的空间冗余进行优化；(2)对辅助数组利用Elias算法进行压缩；(3)对Elias算法做进一步的优化和改进，使辅助数组的数据压缩比进一步提高。改进后的算法保持了Goeman-Clausen算法的线性空间复杂度，但相对于原算法，空间得到了很大的节省，有效的克服了LCS算法应用于大部分遗传基因序列和N-LCS问题时的空间瓶颈，但改进后的算法对比原算法，时间性能上有一些损失，但是在面对大规模序列时候，空间因素显得更为突出。