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: https://drops.dagstuhl.de/opus/volltexte/2017/7322/
Bannai, Hideo ; Inenaga, Shunsuke ; Köppl, Dominik
Computing All Distinct Squares in Linear Time for Integer Alphabets
| pdf-format: |
|
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 | |
| Seminar: | 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 30.06.2017 |
