文章基本信息

标题：Computing All Distinct Squares in Linear Time for Integer Alphabets
本地全文：下载
作者：Hideo Bannai ; Shunsuke Inenaga ; Dominik K{\"o}ppl 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：78
页码：22:1-22:18
DOI：10.4230/LIPIcs.CPM.2017.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：tandem repeats; distinct squares; counting algorithms