Longest common subsequences
Open accessThe DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
The length of a longest common subsequence (LLCS) of two or more strings is a useful measure of their similarity. The LLCS of a pair of strings is related to the `edit distance'', or number of mutations/errors/editing steps required in passing from one string to the other. In this talk, we explore some of the combinatorial properties of the sub- and super-sequence relations, survey various algorithms for computing the LLCS, and introduce some results on the expected LLCS for pairs of random strings.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Handbook of theoretical computer science
Leeuwen, J. V. (1990) · Medical Entomology and Zoology · Cited by 4,259
The String-to-String Correction Problem
Wagner, R. A., & Fischer, M. J. (1974) · Journal of the ACM · doi:10.1145/321796.321811 · Cited by 3,032 · cited 1×
“The algorithm presented by Wagner and Fischer [ 31 ] belongs now among classical dynamic programming methods.”
MethodTime Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison
Sankoff, D., & Kruskal, J. B. (1983) · Medical Entomology and Zoology · Cited by 1,915
A linear space algorithm for computing maximal common subsequences
Hirschberg, D. S. (1975) · Communications of the ACM · doi:10.1145/360825.360861 · Cited by 1,093 · cited 1×
“Hirschberg [ 16 ] gave a variation of the dynamic programming algorithm, that computes D using only linear space.”
BackgroundAlgorithms for the Longest Common Subsequence Problem
Hirschberg, D. S. (1977) · Journal of the ACM · doi:10.1145/322033.322044 · Cited by 750
A fast algorithm for computing longest common subsequences
Hunt, J. W., & Szymanski, T. G. (1977) · Communications of the ACM · doi:10.1145/359581.359603 · Cited by 691 · cited 1×
“Hunt and Szymanski [ 20 ] improved the dynamic programming algorithm by computing only those entries of matrix D that correspond to matches between symbols from u and v. These are typeset in bold in Figure 1. Hirschberg [17] concentrates on dominant matches (circled in Figure 1). A match x +-+ y is dominant if L(ux, v…”
MethodA faster algorithm computing string edit distances
Masek, W. J., & Paterson, M. S. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90002-1 · Cited by 651 · cited 2×
“Only the algorithm in [ 26 ] improves on this, and then only by a logarithmic factor.”
MethodSelf-citationThe Complexity of Some Problems on Subsequences and Supersequences
Maier, D. (1978) · Journal of the ACM · doi:10.1145/322063.322075 · Cited by 616 · cited 1×
“This is an exponential algorithm in terms of l, and there is little expectation of a polynomial algorithm, since Maier [ 25 ] has shown this problem to be NP-complete.”
MethodAlgorithms for approximate string matching
Ukkonen, E. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80046-2 · Cited by 610 · cited 1×
“Ukkonen [ 29 ] formulates the problem of finding longest common subsequences in terms of directed graphs.”
BackgroundA variational problem for random Young tableaux
Logan, B. F., & Shepp, L. A. (1977) · Advances in Mathematics · doi:10.1016/0001-8708(77)90030-5 · Cited by 521
Cited by
Elhadi, M., & Al-Tobi, A. (2009) · 2009 Fourth International Conference on Computer Sciences and Convergence Information Technology · doi:10.1109/iccit.2009.235 · Cited by 32
Metadata
- Authors
- Paterson, M., & Dančík, V.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 1994
- Pages
- 127-142
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1948141881
- Cited by
- 165
- References
- 18
- FWCI
- 2.08
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Longest common subsequences. https://app.cochat.ai/papers/10.1007/3-540-58338-6_63
- The paper
- Paterson, M., & Dančík, V. (1994). Longest common subsequences. Lecture Notes in Computer Science. https://doi.org/10.1007/3-540-58338-6_63
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.