Abstract We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string w , a bidirectional macro scheme of size $$ O ( r_B{} )$$ O ( r B ) can be induced from the BBWT of w , where $$ r_B{} $$ r B is the number of maximal same-symbol runs in the BBWT. We also show that $$ r_B{} = O ( z \, \log ^{ 2 }\, n ) $$ r B = O ( z log 2 n ) , where n is the length of w and z is the number of Lempel-Ziv 77 factors of w . Then, we show a separation between BBWT and BWT by a family of strings with $$ r_B{} = \Omega ( \log \, n ) $$ r B = Ω ( log n ) but having only $$ r= 2 $$ r = 2 , where $${r}$$ r is the maximal same-symbol runs in the standard Burrows–Wheeler transform (BWT). However, we observe that the smallest $$ r_B{} $$ r B among all cyclic rotations of w is always at most $$ r{} $$ r . While computing an optimal rotation yielding the smallest $$ r_B$$ r B in $$ o ( n ^ {2} ) $$ o ( n 2 ) time remains an open problem, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O ( n ) time using right and left Lyndon trees. We also show that the optimal rotations can be computed in $$ \tilde{O} (nh) $$ O ~ ( n h ) time, where

A Lyndon word is a word that is lexicographically smaller than all of its non-trivial rotations (e.g. ananas is a Lyndon word; banana is not a Lyndon word due to its smaller rotation abanan). The Lyndon forest (or equivalently Lyndon table) identifies maximal Lyndon factors of a word, and is of great combinatoric interest, e.g. when finding maximal repetitions in words. While optimal linear time algorithms for computing the Lyndon forest are known, none of them work in an online manner. We present algorithms that compute the Lyndon forest of a word in a reverse online manner, processing the input word from back to front. We assume a general ordered alphabet, i.e. the only elementary operations on symbols are comparisons of the form less-equal-greater. We start with a naive algorithm and show that, despite its quadratic worst-case behaviour, it already takes expected linear time on words drawn uniformly at random. We then introduce a much more sophisticated algorithm that takes linear time in the worst case. It borrows some ideas from the offline algorithm by Bille et al. (ICALP 2020), combined with new techniques that are necessary for the reverse online setting. While the back-to-front approach for this computation is rather natural (see Franek and Liut, PSC 2019), the steps required to achieve linear time are surprisingly intricate. We envision that our algorithm will be useful for the online computation of maximal repetitions in words.

Given a string T of length n over an alphabet Σ ⊂ {1,2,…,n^{𝒪(1)}} of size σ, we are to preprocess T so that given a range [i,j], we can return a representation of a shortest string over Σ that is absent in the fragment T[i]⋯ T[j] of T. For any positive integer k ∈ [1,log log_σ n], we present an 𝒪((n/k)⋅ log log_σ n)-size data structure, which can be constructed in 𝒪(nlog_σ n) time, and answers queries in time 𝒪(log log_σ k).

Abstract A wordxthat is absent from a wordyis calledminimalif all its proper factors occur iny. Given a collection ofkwordsy1, … ,ykover an alphabetΣ, we are asked to compute the set $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ of minimal absent words of length at mostℓof the collection {y1, … ,yk}. The set $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ contains all the wordsxsuch thatxis absent from all the words of the collection while there existi,j, such that the maximal proper suffix ofxis a factor ofyiand the maximal proper prefix ofxis a factor ofyj. In data compression, this corresponds to computing the antidictionary ofkdocuments. In bioinformatics, it corresponds to computing words that are absent from a genome ofkchromosomes. Indeed, the set $\mathrm {M}^{\ell }_{y}$ Myℓ of minimal absent words of a wordyis equal to $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ for any decomposition ofyinto a collection of wordsy1, … ,yksuch that there is an overlap of length at leastℓ− 1 between any two consecutive words in the collection. This computation generally requiresΩ(n) space forn= |y| using any of the plenty available $\mathcal {O}(n)$ O(n) -time algorithms. This is because anΩ(n)-sized text index is constructed overywhich can be impractical for largen. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when $\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| =o(n)$ ∥M{y1,…,yN}ℓ∥=o(n) , for allN∈ [1,k], where ∥S∥ denotes the sum of the lengths of words in setS. For instance, in the human genome,n≈ 3 × 109but $\| \mathrm {M}^{12}_{\{y_1,\ldots ,y_k\}}\| \approx 10^{6}$ ∥M{y1,…,yk}12∥≈106 . We consider a constant-sized alphabet for stating our results. We show thatall $\mathrm {M}^{\ell }_{y_{1}},\ldots ,\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ My1ℓ,…,M{y1,…,yk}ℓ can be computed in $\mathcal {O}(kn+{\sum }^{k}_{N=1}\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| )$ O(kn+∑N=1k∥M{y1,…,yN}ℓ∥) total time using $\mathcal {O}(\textsc {MaxIn}+\textsc {MaxOut})$ O(MaxIn+MaxOut) space, where MaxIn is the length of the longest word in {y1, … ,yk} and $\textsc {MaxOut}=\max \limits \{\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| :N\in [1,k]\}$ MaxOut=max{∥M{y1

A string S[1,n] is a power (or repetition or tandem repeat) of order k and period n/k, if it can be decomposed into k consecutive identical blocks of length n/k. Powers and periods are fundamental structures in the study of strings and algorithms to compute them efficiently have been widely studied. Recently, Fici et al. (Proc. ICALP 2016) introduced an antipower of order k to be a string composed of k distinct blocks of the same length, n/k, called the antiperiod. An arbitrary string will have antiperiod t if it is prefix of an antipower with antiperiod t. In this paper, we describe efficient algorithm for computing the smallest antiperiod of a string S of length n in O(n) time. We also describe an algorithm to compute all the antiperiods of S that runs in O(n log n) time.

A word x that is absent from a word y is called minimal if all its proper factors occur in y. Given a collection of k words y1, y2,...,ykover an alphabet Σ, we are asked to compute the set M(y1#...#yk)ℓof minimal absent words of length at most ℓ of word y=y1#y2#...#yk, #∉Σ. In data compression, this corresponds to computing the antidictionary of k documents. In bioinformatics, it corresponds to computing words that are absent from a genome of k chromosomes. This computation generally requires Ω(n) space for n=|y| using any of the plenty available O(n)-time algorithms. This is because an Ω(n)-sized text index is constructed over y which can be impractical for large n. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when ||M(y1#...#yN)ℓ|| =o(n), for all N ϵ[1, k]. For instance, in the human genome, n ≈ 3 × 109but ||M (y1#...#yk)12|| ≈ 106. We consider a constant-sized alphabet for stating our results. We show that all M(y1)ℓ,...,M(y1#...#yk)ℓcan be computed in O(kn+ΣN=1k||M(y1#...#(yN)ℓ||) total time using O(MaxIn+MaxOut) space, where MaxIn is the length of the longest word in y1,...,ykand MaxOut=max{||M (y1)#...#(yN)ℓ||:N ϵ[1, k]. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.

A string S[1,n] is a power (or tandem repeat) of order k and period n/k if it can be decomposed into k consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an anti-power of order k to be a string composed of k pairwise-distinct blocks of the same length (n/k, called anti-period). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string S, we describe an optimal algorithm for locating all substrings of S that are anti-powers of a specified order. The optimality of the algorithm follows form a combinatorial lemma that provides a lower bound on the number of distinct anti-powers of a given order: we prove that a string of length n can contain Θ(n2/k) distinct anti-powers of order k.

Many metaheuristics such as island models and cellular evolutionary algorithms use a network of distributed populations that communicate search points along a spatial communication topology. The idea is to slow down the spread of information, reducing the risk of "premature convergence", and sacrificing exploitation for an increased exploration.