算法在1981年提出，是在算法发展而来的一种知名的LCS算法，并被证明是正确的。Aho 和eral通过决策树模型[3]计算出时间下限为O(mn)。通过动态规划算法[4]，这个问题能够用O(mn)的空间和O(mn)的时间解决。Mayers和Miller使用Hirschberg提出的技术在同样的时间精度下将空间效率降低至O(m+n)。87037

为了更多地减少计算时间，一些不同计算模型下的并发算法被提出。对于CREW-PRAM模型，Aggarwal和Apostolicoetal各自独立的提出使用mn/logm 个处理器，时间效率为O(logmlogn)的算法。Luetal设计了两个并发LCS算法，一个使用mn/logm个处理器，时间效率为O(log2n+logm),另一个使用mn/(log2mloglogm)个处理器，时间效率为O(log2mloglogm)。Apostolicoetal提出了使用mn/loglogm个处理器，时间效率为的算法。Babu和Saxena优化了这些算法，他们提出使用mn个处理器时间复杂度为O(log2n)的并发算法。很多并发LCS算法也提出使用收缩阵列[5]，Robertetal提出使用m(m+1)个处理器，需要n+5m步骤的算法。Changetal提出使用mn个处理元素，需要4n+2m步骤的算法。Luceetal设计了一个带有m(m+1)/2个处理器的收缩阵列，需要n+3m+q步骤的算法（其中q是LCS的长度）。Freschi和Bogliolo提出计算RLE字符串的LCS的问题。他们的算法通过使用M+N个处理器元素的收缩阵列需要O(m+n)步骤的算法（M和N分别为相应字符串的长度，m和n运行在游程编码的相应长度）。论文网

如果求解多个字符序列的公共子序列，时间复杂度会随着字符序列的增长急剧增长。比如，若是使用Smith-Waterman算法去求解多个字符序列的LCS问题，时间复杂度就变为，其中n是字符序列的数量，是相应字符序列的第i个字符。当n变得非常大时，算法就不可行。一些优化在此基础上就提出来了。MSA算法能够处理多达10个字符序列。从Carrillo和Lipman算法可以看出，对多维空间拆分并不能解决问题和免除计算。Stoye提出了一个继承自MSA算法的分而治之算法的DCA算法[6]。最近DCA的迭代实现算法OMA被证明能够提高DCA的效率和减少内存需求。基于Feng和Doolittle的算法，Clustal-W被认为是在LCS计算上应用最为广泛的多字符序列匹配软件。