  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 non-overlapping 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 length-$n$ string in $O(n \log n)$ time. We show how to
compute the CST in $O(n)$ time assuming that $T$ is over an integer alphabet.
  Kociumaka et al. (Algorithmica, 2015; Theor. Comput. Sci., 2018) have shown
that knowing the CST of a length-$n$ string $T$, one can compute a linear-sized
representation of all seeds of $T$ as well as all shortest $\alpha$-partial
covers and seeds in $T$ for a given $\alpha$ in $O(n)$ time. Thus our result
implies linear-time 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).
Kociumaka et al. (Algorithmica, 2015) proposed an $O(n \log n)$-time algorithm
for computing a shortest $\alpha$-partial cover for each $\alpha=1,\ldots,n$;
we improve this complexity to $O(n)$.
  Our results are based on a new 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 $O(n)$-sized
index for reporting overlapping consecutive occurrences of a given pattern $P$
of length $m$ in $O(m+output)$ time, where $output$ is the number of
occurrences reported. In comparison, a general index for reporting bounded-gap
consecutive occurrences of Navarro and Thankachan (Theor. Comput. Sci., 2016)
uses $O(n \log n)$ space.
