Computing the Number of Longest Common Subsequences

2003/01/29 by Ronald I. Greenberg, Greenberg, Ronald I.
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #cs.DM #cs.DS

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

3 pages, LaTeX

arxiv created 2003/01/29 · arxiv updated 2009/11/30

Abstract

This note provides very simple, efficient algorithms for computing the number of distinct longest common subsequences of two input strings and for computing the number of LCS embeddings.

Related

• Bounds on the Number of Longest Common Subsequences
• Efficient algorithms for the longest common subsequence in k-length substrings
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings
• Fast and Simple Computation of All Longest Common Subsequences
• A Data-Structure for Approximate Longest Common Subsequence of A Set of\n Strings