Computing All Distinct Squares in Linear Time for Integer Alphabets

2016/10/11 by Bannai, Hideo, Inenaga, Shunsuke, Köppl, Dominik · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1610.03421

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.

Cited by

• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares
• Counting Distinct Square Substrings in Sublinear Time

Related

• Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
• Optimal Square Detection Over General Alphabets
• Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
• Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
• Longest Square Subsequence Problem Revisited