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
Algorithms for Finding Patterns in Strings
AHO, A. V. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50010-2 · Cited by 373
Bounds on the Complexity of the Longest Common Subsequence Problem
Ullman, J. D., Aho, A. V., & Hirschberg, D. S. (1976) · Journal of the ACM · doi:10.1145/321921.321922 · Cited by 247
Longest common subsequences of two random sequences
Chvátal, V., & Sankoff, D. (1975) · Journal of Applied Probability · doi:10.2307/3212444 · Cited by 240
Sparse dynamic programming I: linear cost functions
Eppstein, D., Galil, Z., Giancarlo, R., & Italiano, G. F. (1992) · Journal of the ACM · doi:10.1145/146637.146650 · Cited by 178
Bounds for the String Editing Problem
Wong, C. K., & Chandra, A. K. (1976) · Journal of the ACM · doi:10.1145/321921.321923 · Cited by 126 · cited 1×
“Wong and Chandra [ 32 ] consider restricted models for deriving lower bounds.”
BackgroundFast linear-space computations of longest common subsequences
Apostolico, A., Browne, S. V., & Guerra, C. F. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90132-y · Cited by 60
Expected length of longest common subsequences
Dancík, V. (2026) · Warwick Research Archive Portal (University of Warwick) · doi:10.82444/warw.33764206 · Cited by 52
Maximal common subsequences and minimal common supersequences
Irving, R. W., & Fraser, C. B. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58094-8_16 · Cited by 5
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
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.