最长公共子序列(LCS)是将两条序列分别删去零个或多个元素后得到的长度最长的相同元素序列。LCS的应用包括文本相似度检测,基因序列比对等。给定两个序列,本文研究如何快速求解最长公共子序列,返回它们的长度,具体研究内容如下。首先,通过对现有算法进行分析,发现现有的算法存在效率低、扩展性差的问题。针对这些问题,提出一种层次索引,并提出相应的索引构建算法LEVEL-LCS。该算法首先对较长序列按字符建立倒排索引,然后结合较短序列构建层次LCS索引结构。通过自底向上的遍历该索引,可枚举出给定两序列的所有最长公共子序列以及长度。和传统动态规划的方法相比,减少了非必要字符对的匹配计算及其结果的存储,从而提升效率,降低了存储空间。其次,为了进一步减少索引空间,提出高效的剪枝策略,并设计了相应的索引构建算法LEVEL-LCS+。该优化算法将层次LCS索引结构中相邻的重复值用单一值代替,进一步降低了存储空间,并提高了枚举过程的效率。在仅需计算最长公共子序列长度的情况下,提出了LENGTH-LCS算法,将算法空间复杂度降低至线性。最后,基于多组真实数据集和人工数据集进行测试,实验结果从构建索引时间,索引占用空间大小等方面进行了比较,实验结果验证了本文所提出方法的高效性和扩展性。