Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.1
URN: urn:nbn:de:0030-drops-87079
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8707/
Sakai, Yoshifumi
Maximal Common Subsequence Algorithms
| pdf-format: |
|
Abstract
A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal.
BibTeX - Entry
@InProceedings{sakai:LIPIcs:2018:8707,
author = {Yoshifumi Sakai},
title = {{Maximal Common Subsequence Algorithms}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {1:1--1:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8707},
URN = {urn:nbn:de:0030-drops-87079},
doi = {10.4230/LIPIcs.CPM.2018.1},
annote = {Keywords: algorithms, string comparison, longest common subsequence, constrained longest common subsequence}
}
| Keywords: | algorithms, string comparison, longest common subsequence, constrained longest common subsequence | |
| Seminar: | Annual Symposium on Combinatorial Pattern Matching (CPM 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 18.05.2018 |
