Author name cluster

Tomasz Waleń

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

1 author row

TCS Journal 2026 Journal Article

Internal quasiperiod queries

Maxime Crochemore
Costas S. Iliopoulos
Jakub Radoszewski
Wojciech Rytter
Juliusz Straszyński
Tomasz Waleń
Wiktor Zuba

Internal pattern matching requires one to answer queries about factors of a given string. Many results are known on answering internal period queries, asking for the periods of a given factor. In this paper we investigate internal queries asking for covers (also known as quasiperiods) of a given factor. Let n denote the length of the string and m denote the length of the factor in question. We propose a data structure that answers such queries in O ( log m ) time for the shortest cover and in O ( log m log log m ) time for a representation of all the covers, after O ( n log n ) time and space preprocessing. This is a full version of a conference paper at SPIRE 2020 with query complexities improved by a log log n-factor and additional applications.

TCS Journal 2026 Journal Article

Quasi-linear-time algorithm for a longest common circular factor

Mai Alzamel
Maxime Crochemore
Costas S. Iliopoulos
Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Juliusz Straszyński
Tomasz Waleń

We consider the Longest Common Circular Factor (LCCF) problem in which, given strings S and T of length at most n, we are to compute the longest factor of S whose cyclic shift is a factor of T. This new similarity measure is an extension of the classic Longest Common Factor. We show an algorithm solving the LCCF problem in O ( n log 3 n log ( r + 2 ) ) time, where r ≤ n is the length of the output, using O ( n ) space. A naive algorithm works in Ω(n 2) time, and no O ( n polylog n ) -time solution was known prior to our work. Our result constitutes yet another application of string synchronizing sets of Kempa and Kociumaka (STOC 2019). Compared to the preliminary version published at CPM 2019, we significantly simplified the algorithm and improved the space complexity from O ( n log 2 n ) to O ( n ). We achieved that with new algorithmic insights into a certain geometric intersection problem, solved by suitably decomposing intervals.

TCS Journal 2025 Journal Article

Subsequence covers of words

Panagiotis Charalampopoulos
Solon P. Pissis
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń
Wiktor Zuba

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].

I&C Journal 2022 Journal Article

A periodicity lemma for partial words

Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

We investigate the function L ( h, p, q ), called here the length function, such that L ( h, p, q ) is the minimum length which guarantees that a natural extension of the periodicity lemma is valid for partial words with h holes and (so-called strong) periods p, q. In a series of papers, the formulae for the length function, in terms of p and q, were provided for each fixed h ≤ 7. We demystify the generic structure of such formulae and give a complete characterization of the length function for any parameter h expressed in terms of a piecewise-linear function with O ( h ) pieces. We also show how to evaluate the length function in O ( log ⁡ p + log ⁡ q ) time, which is an improvement upon the best previously known O ( p + q ) -time algorithm.

I&C Journal 2022 Journal Article

Efficient representation and counting of antipower factors in words

Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Juliusz Straszyński
Tomasz Waleń
Wiktor Zuba

A k-antipower (for k ≥ 2 ) is a concatenation of k distinct words of the same length. Fici et al. (ICALP 2016) initiated the study of antipowers occurring as fragments of a word, whereas Badkobeh et al. (Inf. Process. Lett. , 2018) presented first algorithms computing such fragments. We address two open problems originating from the latter work and propose efficient algorithms for counting and reporting fragments being k-antipowers. For a length-n word, our algorithms cost O ( n k log ⁡ k ) and O ( n k log ⁡ k + C ) time, respectively, where C is the number of reported fragments. We also show that the number of different k-antipower factors of a length-n word can be computed in O ( n k 4 log ⁡ k log ⁡ n ) time. Finally, we present an improved data structure that checks whether a given fragment is a k-antipower for a given integer k ≥ 2. Our main algorithmic tools are runs and maximal gapped repeats.

TCS Journal 2021 Journal Article

Shortest covers of all cyclic shifts of a string

Maxime Crochemore
Costas S. Iliopoulos
Jakub Radoszewski
Wojciech Rytter
Juliusz Straszyński
Tomasz Waleń
Wiktor Zuba

A factor C of a string S is called a cover of S, if each position of S is contained in an occurrence of C. Breslauer (1992) [3] proposed a well-known O ( n ) -time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O ( n log ⁡ n ) -time and O ( n ) -space algorithm that computes the shortest cover of every cyclic shift of a string of length n and an O ( n ) -time algorithm that computes the shortest among these covers. We also provide a combinatorial characterization of shortest covers of cyclic shifts of Fibonacci strings that leads to efficient algorithms for computing these covers. We further consider the bound on the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Θ ( log ⁡ n ) for Fibonacci strings.

I&C Journal 2020 Journal Article

String periods in the order-preserving model

Garance Gourdel
Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Arseny Shur
Tomasz Waleń

In the order-preserving model, two strings match if they share the same relative order between the characters at the corresponding positions. This model is quite recent, but it has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O ( n ), O ( n log ⁡ log ⁡ n ), O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ), O ( n log ⁡ n ) depending on the type of periodicity. In the most general variant, the number of different op-periods can be as big as Ω ( n 2 ), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of op-periods. In particular, we characterize the Fine–Wilf property for coprime op-periods.

TCS Journal 2020 Journal Article

Universal reconstruction of a string

Paweł Gawrychowski
Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

Many properties of a string can be viewed as sets of dependencies between substrings of the string expressed in terms of substring equality. We design a linear-time algorithm which finds a solution to an arbitrary system of such constraints: a generic string satisfying a system of substring equations. This provides a general tool for reconstructing a string from different kinds of repetitions or symmetries present in the string, in particular, from runs or from maximal palindromes. The recursive structure of our algorithm in some aspects resembles the suffix array construction by Kärkkäinen et al. (2006) [23]. This is a full version of a paper presented at WADS 2015 [18].

TCS Journal 2018 Journal Article

Efficient algorithms for shortest partial seeds in words

Tomasz Kociumaka
Solon P. Pissis
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al. , 2015, [13]); an O ( n log ⁡ n ) -time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O ( n ) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

TCS Journal 2018 Journal Article

On the string consensus problem and the Manhattan sequence consensus problem

Tomasz Kociumaka
Jakub W. Pachocki
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

We study the Manhattan Sequence Consensus problem (MSC problem) in which we are given k integer sequences, each of length ℓ, and we are to find an integer sequence x of length ℓ (called a consensus sequence) such that the maximum Manhattan distance of x from each of the input sequences is minimized. A related problem, with Hamming distance instead of Manhattan distance, is called Hamming String Consensus (HSC), also known under the names of string center problem or closest string problem. For binary sequences Manhattan distance coincides with Hamming distance, hence in this case HSC is a special case of MSC. We design a practically efficient O ( ℓ ) -time algorithm solving MSC for k ≤ 5 sequences. It improves upon the quadratic algorithm by Amir et al. (2012) [1] for HSC for k = 5 binary strings. Similarly as in the algorithm of Amir et al. , we use a column-based framework. We replace the implied general integer linear programming by its easy special cases due to combinatorial properties of MSC for k ≤ 5. Practicality of our algorithms has been verified experimentally. We also show that for a general parameter k any instance can be reduced in linear time to a kernel of size k! , so the problem is fixed-parameter tractable. Nevertheless, for k ≥ 4 this is still too large for any naive solution to be feasible in practice. This is a full version of an article published at SPIRE 2014 [15].

TCS Journal 2017 Journal Article

Covering problems for partial words and for indeterminate strings

Maxime Crochemore
Costas S. Iliopoulos
Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

Indeterminate strings are a subclass of non-standard words having non-deterministic nature. In a classic string every position contains exactly one symbol—we say it is a solid symbol—while in an indeterminate string a position may contain a set of symbols (possible at this position); such sets are called non-solid symbols. The most important subclass of indeterminate strings are partial words, where each non-solid symbol is the whole alphabet; in this case non-solid symbols are also called don't care symbols. We consider the problem of finding a shortest cover of an indeterminate string, i. e. , finding a shortest solid string whose occurrences cover the whole indeterminate string. We show that this classical problem becomes NP-complete for indeterminate strings and even for partial words. The proof of this fact is one of the main results of this paper. Our other main results focus on design of algorithms efficient with respect to certain parameters of the input (so called FPT algorithms) for the shortest cover problem. For the indeterminate string covering problem we obtain an O ( n k 2 + 2 k k 3 ) -time algorithm, where k is the number of non-solid symbols, while for the partial word covering problem we obtain a running time of O ( n k 2 + 2 O ( k log ⁡ k ) ). Additionally, we prove that, unless the Exponential Time Hypothesis is false, no 2 o ( k ) n O ( 1 ) -time solution exists for either problem, which shows that our algorithm for partial words is close to optimal. We also present an algorithm for both problems parameterized both by k and the alphabet size with a simple implementation. A preliminary version of this article was presented at the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS, vol. 8889, pp. 220–232, Springer (2014) [12].

TCS Journal 2016 Journal Article

Maximum number of distinct and nonequivalent nonstandard squares in a word

Tomasz Kociumaka
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

The combinatorics of nonstandard squares in a word depends on how the equivalence of halves of the square is defined. We consider Abelian squares, parameterized squares, and order-preserving squares. The word uv is an Abelian (parameterized, order-preserving) square if u and v are equivalent in the Abelian (parameterized, order-preserving) sense. The maximum number of ordinary squares in a word is known to be asymptotically linear, but the exact bound is still investigated. We present several results on the maximum number of distinct squares for nonstandard factor equivalence relations. Let SQ Abel ( n, σ ) and SQ Abel ′ ( n, σ ) denote the maximum number of Abelian squares in a word of length n over an alphabet of size σ which are distinct as words and which are nonequivalent in the Abelian sense, respectively. For σ ≥ 2 we prove that SQ Abel ( n, σ ) = Θ ( n 2 ), SQ Abel ′ ( n, σ ) = Ω ( n 3 / 2 ) and SQ Abel ′ ( n, σ ) = O ( n 11 / 6 ). We also give linear bounds for parameterized and order-preserving squares for alphabets of constant size: SQ param ( n, O ( 1 ) ) = Θ ( n ), SQ op ( n, O ( 1 ) ) = Θ ( n ). The upper bounds have quadratic dependence on the alphabet size for order-preserving squares and exponential dependence for parameterized squares. As a side result we construct infinite words over the smallest alphabet which avoid nontrivial order-preserving squares and nontrivial parameterized cubes (nontrivial parameterized squares cannot be avoided in an infinite word). A preliminary version of this paper was published at DLT 2014 [24]. In this full version we improve or extend the bounds on all three kinds of squares.

TCS Journal 2016 Journal Article

Order-preserving indexing

Maxime Crochemore
Costas S. Iliopoulos
Tomasz Kociumaka
Marcin Kubica
Alessio Langiu
Solon P. Pissis
Jakub Radoszewski
Wojciech Rytter

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees.

TCS Journal 2014 Journal Article

Efficient counting of square substrings in a tree

Tomasz Kociumaka
Jakub Pachocki
Jakub Radoszewski
Wojciech Rytter
Tomasz Waleń

We give an algorithm which in O ( n log 2 n ) time counts all distinct squares in a labeled tree. There are two main obstacles to overcome. The first one is that the number of distinct squares in a tree is Ω ( n 4 / 3 ) (see Crochemore et al. , 2012 [7]), which differs substantially from the case of classical strings for which there are only linearly many distinct squares. We overcome this obstacle by using a compact representation of all squares (based on maximal cyclic shifts) which requires only O ( n log n ) space. The second obstacle is lack of adequate algorithmic tools for labeled trees, consequently we design several novel tools, this is the most complex part of the paper. In particular we extend to trees Imre Simon's compact representations of the failure table in pattern matching machines.

TCS Journal 2012 Journal Article

Improved algorithms for the range next value problem and applications

Maxime Crochemore
Costas S. Iliopoulos
Marcin Kubica
M. Sohel Rahman
German Tischler
Tomasz Waleń

The Range Next Value problem (problem RNV) is a recent interesting variant of the range search problems, where the query is for the immediate next (or equal) value of a given number within a given interval of an array. Problem RNV was introduced and studied very recently by Crochemore et al. [Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman, Finding patterns in given intervals, in: Antonin Kucera, Ludek Kucera (Eds.), MFCS, 22 in: Lecture Notes in Computer Science, vol. 4708, Springer, 2007, pp. 645–656]. In this paper, we present improved algorithms for problem RNV and algorithms for extended versions of the RNV problem. We also show how this problem can be used to achieve optimal query time for a number of interesting variants of the classic pattern matching problems.