The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
A survey of longest common subsequence algorithms
Abstract
The aim of this paper is to give a comprehensive comparison of well-known longest common subsequence algorithms (for two input strings) and study their behaviour in various application environments. The performance of the methods depends heavily on the properties of the problem instance as well as the supporting data structures used in the implementation. We want to make also a clear distinction between methods that determine the actual lcs and those calculating only its length, since the execution time and more importantly, the space demand depends crucially on the type of the task. To our knowledge, this is the first time this kind of survey has been done. Due to the page limits, the paper gives only a coarse overview of the performance of the algorithms; more detailed studies are reported elsewhere.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Improved tools for biological sequence comparison.
Pearson, W. R., & Lipman, D. J. (1988) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.85.8.2444 · Cited by 11,227
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Gusfield, D. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511574931 · Cited by 3,078
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
Algorithms on strings, trees, and sequences
Gusfield, D. (1997) · Cited by 1,697
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
AnO(ND) difference algorithm and its variations
Myers, E. W. (1986) · Algorithmica · doi:10.1007/bf01840446 · Cited by 893
Algorithms 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
A 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 by
Time-series clustering – A decade review
Aghabozorgi, S., Seyed Shirkhorshidi, A., & Ying Wah, T. (2015) · Information Systems · doi:10.1016/j.is.2015.04.007 · Cited by 1,826
From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews
McAuley, J. J., & Leskovec, J. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488466 · Cited by 525
Studer, M., & Ritschard, G. (2016) · Journal of the Royal Statistical Society Series A: Statistics in Society · doi:10.1111/rssa.12125 · Cited by 500
Social fingerprinting: detection of spambot groups through DNA-inspired behavioral modeling
Cresci, S., Di Pietro, R., Petrocchi, M., Spognardi, A., & Tesconi, M. (2017) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2017.2681672 · Cited by 168
Use of text syntactical structures in detection of document duplicates
Elhadi, M., & Al-Tobi, A. (2008) · 2008 Third International Conference on Digital Information Management · doi:10.1109/icdim.2008.4746719 · Cited by 36
Metadata
- Authors
- Bergroth, L., Hakonen, H., & Raita, T.
- Venue
- Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-07
- Pages
- 39-48
- OpenAlex
- W2109227373
- Cited by
- 655
- References
- 19
- FWCI
- 2.99
- Type
- conference paper
- Language
- en
- Open access
- closed
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: A survey of longest common subsequence algorithms. https://app.cochat.ai/papers/10.1109/spire.2000.878178
- The paper
- Bergroth, L., Hakonen, H., & Raita, T. (2002). A survey of longest common subsequence algorithms. Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000. https://doi.org/10.1109/spire.2000.878178
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.