Author name cluster

Juliusz Straszyński

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.

4 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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI