2026-07-25T00:39:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7322 2024-03-06T10:40:08Z ddc:004 open_access

Computing All Distinct Squares in Linear Time for Integer Alphabets Bannai, Hideo Inenaga, Shunsuke Köppl, Dominik tandem repeats distinct squares counting algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hideo Bannai and Shunsuke Inenaga and Dominik Köppl 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.22 urn:nbn:de:0030-drops-73224 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.22 eng https://creativecommons.org/licenses/by/3.0/legalcode