最长公共子序列问题是计算机科学领域的一个经典问题,用于返回多个序列的最长公共子序列,简称为MLCS。MLCS问题在基因检测、序列相似性比对、模式识别、数据挖掘、代码克隆检测、文献查重、网页聚类等领域有着重要应用。目前求解MLCS问题通常采用基于动态规划的算法和基于匹配点的算法。随着字符序列数量和长度的增长,已有算法从效率和扩展性的角度不能满足实际需求。本文针对MLCS问题进行研究,研究内容如下。首先,提出一种基于单哈希的最长公共子序列算法SF_MLCS,该算法首先按序列中字符间后继关系生成每个序列的后继表,进而用有向无环图表示所有序列的后继表。在此基础上,通过哈希的方式快速存取字符间的后继关系。和已有方法采用双哈希来记录前驱及后继的方式相比,本文提出的单哈希方法在提升效率的同时,降低了所用内存空间。其次,针对单哈希方法空间代价高,无法处理长序列的问题,提出一种基于分治策略的最长公共子序列算法DC_MLCS算法。基于表示所有序列后继表的有向无环图,DC_MLCS算法首先预处理生成基于前pre_level层匹配顶点的子图,然后对该子图中所有出度为零的顶点逐一处理,在处理每个顶点时,删除前一个被处理顶点所占用空间,从而降低了系统的空间代价,可以处理更长的序列。并在此基础上提出了top-k最长公共子序列的概念,设计和实现相应的算法来求解给定的n个序列中,所有k个序列的最长公共子序列中最长的公共子序列。最后,基于真实数据集进行实验,验证了本文算法的高效性。