Abstract
The Cover Suffix Tree (CST) of a string T is the suffix tree of T with additional explicit nodes corresponding to halves of square substrings of T. In the CST an explicit node corresponding to a substring C of T is annotated with two numbers: the number of nonoverlapping consecutive occurrences of C and the total number of positions in T that are covered by occurrences of C in T. Kociumaka et al. (Algorithmica, 2015) have shown how to compute the CST of a lengthn string in 𝒪(n log n) time. We give an algorithm that computes the same data structure in 𝒪(n) time assuming that T is over an integer alphabet and discuss its implications.
A string C is a cover of text T if occurrences of C in T cover all positions of T; C is a seed of T if occurrences and overhangs (i.e., prefixsuffix occurrences) of C in T cover all positions of T. An αpartial cover (αpartial seed) of text T is a string C whose occurrences in T (occurrences and overhangs in T, respectively) cover at least α positions of T. Kociumaka et al. (Algorithmica, 2015; Theor. Comput. Sci., 2018) have shown that knowing the CST of a lengthn string T, one can compute a linearsized representation of all seeds of T as well as all shortest αpartial covers and seeds in T for a given α in 𝒪(n) time. Thus our result implies lineartime algorithms computing these notions of quasiperiodicity. The resulting algorithm computing seeds is substantially different from the previous one (Kociumaka et al., SODA 2012, ACM Trans. Algorithms, 2020); in particular, it is nonrecursive. Kociumaka et al. (Algorithmica, 2015) proposed an 𝒪(n log n)time algorithm for computing a shortest αpartial cover for each α = 1,…,n; we improve this complexity to 𝒪(n).
Our results are based on a new combinatorial characterization of consecutive overlapping occurrences of a substring S of T in terms of the set of runs (see Kolpakov and Kucherov, FOCS 1999) in T. This new insight also leads to an 𝒪(n)sized index for reporting overlapping consecutive occurrences of a given pattern P of length m in the optimal 𝒪(m+output) time, where output is the number of occurrences reported. In comparison, a general index for reporting boundedgap consecutive occurrences of Navarro and Thankachan (Theor. Comput. Sci., 2016) uses 𝒪(n log n) space.
BibTeX  Entry
@InProceedings{radoszewski:LIPIcs.ESA.2023.89,
author = {Radoszewski, Jakub},
title = {{Linear Time Construction of Cover Suffix Tree and Applications}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {89:189:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18742},
URN = {urn:nbn:de:0030drops187428},
doi = {10.4230/LIPIcs.ESA.2023.89},
annote = {Keywords: cover (quasiperiod), seed, suffix tree, run (maximal repetition)}
}
Keywords: 

cover (quasiperiod), seed, suffix tree, run (maximal repetition) 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 