Computing the Number of Longest Common Subsequences

Ronald I. Greenberg

Computing the Number of Longest Common Subsequences

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
State	Published - Jan 1 2003

Keywords

longest common subsequences
edit distance
shortest common supersequences

Disciplines

Computer Sciences
Discrete Mathematics and Combinatorics
Theory and Algorithms

Access to Document

https://arxiv.org/pdf/cs/0301034.pdf

Cite this

@article{50d268284e074a7085ceba0c988c3993,

title = "Computing the Number of Longest Common Subsequences",

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.",

keywords = "longest common subsequences, edit distance, shortest common supersequences",

author = "Greenberg, \{Ronald I.\}",

note = "Ronald I. Greenberg. Computing the number of longest common subsequences. Technical report, Computer Science Research Repository (http://arXiv.org), 2003. Article ID cs/0301034v1.",

year = "2003",

month = jan,

day = "1",

language = "American English",

journal = "Computer Science: Faculty Publications and Other Works",

}

TY - JOUR

T1 - Computing the Number of Longest Common Subsequences

AU - Greenberg, Ronald I.

N1 - Ronald I. Greenberg. Computing the number of longest common subsequences. Technical report, Computer Science Research Repository (http://arXiv.org), 2003. Article ID cs/0301034v1.

PY - 2003/1/1

Y1 - 2003/1/1

N2 - 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.

AB - 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.

KW - longest common subsequences

KW - edit distance

KW - shortest common supersequences

UR - https://ecommons.luc.edu/cs_facpubs/180

UR - https://arxiv.org/pdf/cs/0301034.pdf

M3 - Article

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

ER -

Computing the Number of Longest Common Subsequences

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this