  Mantaci et al. [TCS 2007] defined the eBWT to extend the definition of the
BWT to a collection of strings, however, since this introduction, it has been
used more generally to describe any BWT of a collection of strings and the
fundamental property of the original definition (i.e., the independence from
the input order) is frequently disregarded. In this paper, we propose a simple
linear-time algorithm for the construction of the original eBWT, which does not
require the preprocessing of Bannai et al. [CPM 2021]. As a byproduct, we
obtain the first linear-time algorithm for computing the BWT of a single string
that uses neither an end-of-string symbol nor Lyndon rotations. We combine our
new eBWT construction with a variation of prefix-free parsing to allow for
scalable construction of the eBWT. We evaluate our algorithm (pfpebwt) on sets
of human chromosomes 19, Salmonella, and SARS-CoV2 genomes, and demonstrate
that it is the fastest method for all collections, with a maximum speedup of
7.6x on the second best method. The peak memory is at most 2x larger than the
second best method. Comparing with methods that are also, as our algorithm,
able to report suffix array samples, we obtain a 57.1x improvement in peak
memory. The source code is publicly available at
https://github.com/davidecenzato/PFP-eBWT.
