Given a set of results from range minimum queries (RMQs), our task is to construct a sequence that is consistent with the results of the queries. We study two types of RMQs: a value-based RMQ returns the minimum value and an index-based RMQ returns the index of the minimum. While the value-based version has been discussed informally in the context of competitive programming, the index-based version appears to be unexplored. In this paper, we provide a survey and unified analysis of the value-based version, and we propose efficient algorithms for the index-based version. These include algorithms for computing the lexicographically smallest consistent sequence and permutation, as well as an enumeration algorithm that outputs all consistent permutations with constant delay. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.

Let w be a string of length n. The problem of counting factors crossing a position - Problem 64 fromthe textbook "125 Problems in Text Algorithms" [Crochemore, Leqroc, and Rytter, 2021], asks to count the number C(w,k) (resp. N(w,k)) of distinct substrings in w that have occurrences containing (resp. not containing) a position k in w. The solutions provided in their textbook compute C(w,k) and N(w,k) in O(n) time for a single positionk in w, and thus a direct application would require O(n2) time for all positionsk=1,…,n in w. Their solution is designed for constant-size alphabets. In this paper, we present new algorithms which compute C(w,k) in O(n) total time for general ordered alphabets, and N(w,k) in O(n) total time for linearly sortable alphabets, for all positions k=1,…,n in w. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.

The Bijective BWT (BBWT), conceived by Scott in 2007, later summarized in a preprint by Gil and Scott in 2009 (arXiv 2012), is a variant of the Burrows-Wheeler Transform which is bijective: every string is the BBWT of some string. Indeed, the BBWT of a string is the extended BWT [Mantaci et al., 2007] of the factors of its Lyndon factorization. The BBWT has been receiving increasing interest in recent years. In this paper, we survey existing research on the BBWT, starting with its history and motivation. We then present algorithmic topics including construction algorithms with various complexities and an index on top of the BBWT for pattern matching. We subsequently address some properties of the BBWT as a compressor, discussing robustness to operations such as reversal, edits, rotation, as well as compression power. We close with listing other bijective variants of the BWT and open problems concerning the BBWT. © Hideo Bannai, Dominik Köppl, and Zsuzsanna Lipták.

An α-ary tree for a constant α ≥ 2 is a rooted tree in which each node has at most α children. A node having no children is called a leaf. For a given rooted tree and a node v, the number of edges from the root to v is called the depth of v. We call a vector w = (w1, w2, . . ., wd) of nonnegative integers an (α-ary) distribution if there is an α-ary tree T such that the number of leaves at each depth i ∈ [1..d] in T is wi. Although not every vector of nonnegative integers is a distribution, a distribution can be associated with many α-ary trees. In this paper, we present an algorithm to enumerate all α-ary trees for a given distribution. Our algorithm reports the first tree in O(d + ∑di=1 wi) time, and then each subsequent α-ary tree in O(maxdi=1 wi) time by representing each tree as the difference from the previous one. The algorithm can be restricted to computing all trees that are full, i.e., trees whose nodes have exactly α or no children. © Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono, Toshiki Saitoh, and Yushi Uno;