License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8707/
Go to the corresponding LIPIcs Volume Portal

Sakai, Yoshifumi

Maximal Common Subsequence Algorithms

pdf-format:
LIPIcs-CPM-2018-1.pdf (0.4 MB)

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
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI