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.2017.22
URN: urn:nbn:de:0030-drops-73224
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7322/
Go to the corresponding LIPIcs Volume Portal

Bannai, Hideo ; Inenaga, Shunsuke ; Köppl, Dominik

Computing All Distinct Squares in Linear Time for Integer Alphabets

pdf-format:
LIPIcs-CPM-2017-22.pdf (0.7 MB)

Abstract

Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear to the string length. As an application, we show how to compute the tree topology of the minimal augmented suffix tree in linear time. Asides from that, we elaborate an algorithm computing the longest previous table in a succinct representation using compressed working space.

BibTeX - Entry

@InProceedings{bannai_et_al:LIPIcs:2017:7322,
  author =	{Hideo Bannai and Shunsuke Inenaga and Dominik K{\"o}ppl},
  title =	{{Computing All Distinct Squares in Linear Time for Integer Alphabets}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7322},
  URN =		{urn:nbn:de:0030-drops-73224},
  doi =		{10.4230/LIPIcs.CPM.2017.22},
  annote =	{Keywords: tandem repeats, distinct squares, counting algorithms}
}

Keywords: tandem repeats, distinct squares, counting algorithms
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

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