Fast and Simple Computation of All Longest Common Subsequences

2002/11/01 by Ronald I. Greenberg, Greenberg, Ronald I.
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Natural Language Processing Techniques

paper · pdf · doi:10.48550/arxiv.cs/0211001

openalex publication_date 2002/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper shows that a simple algorithm produces the \em all-prefixes-LCSs-graph in O(mn) time for two input sequences of size m and n. Given any prefix p of the first input sequence and any prefix q of the second input sequence, all longest common subsequences (LCSs) of p and q can be generated in time proportional to the output size, once the all-prefixes-LCSs-graph has been constructed. The problem can be solved in the context of generating all the distinct character strings that represent an LCS or in the context of generating all ways of embedding an LCS in the two input strings.

Related

• Bounds on the Number of Longest Common Subsequences
• Efficient algorithms for the longest common subsequence in k-length substrings
• Computing the Number of Longest Common Subsequences
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings
• Longest Common Subsequence in k-length substrings