JRJakub Radoszewski

Jakub Radoszewski

University of Warsaw
*This is an algorithmically generated author record based on publicly available information.
See Latest Publications
See Most Cited Publications
SciProfiles
ORCID Profile
Google Scholar

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years

Jakub Radoszewski has a total of 69 co-authors. Here are the top co-authors by number of shared publications:

Latest Publications

  • Website
    Google Scholar

    Computing Smallest Suffixient Arrays in Sublinear Time

    by Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares, Jakub Radoszewski, Giuseppe Romana, Cristian Urbina

  • Website
    Google Scholar

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

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

  • Website
    Google Scholar

    Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words

    by Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

  • Website
    Google Scholar

    Computing String Covers in Sublinear Time

    by Jakub Radoszewski, Wiktor Zuba

  • Website
    Google Scholar
    Open Access

    Faster Algorithms for Longest Common Substring

    by Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis

    In the classic Longest Common Substring (LCS) problem, we are given two strings \( S \) and \( T \) of total length \( n \) over an alphabet of size \(\sigma\) , and we are asked to find a longest string occurring as a fragment of both \( S \) and \( T \) . Weiner, in his seminal paper that introduced the suffix tree, presented an \(\mathcal{O}(n\log\sigma)\) -time algorithm for the LCS problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an \(\mathcal{O}(n)\) -time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in \(\mathcal{O}(n\log\sigma/\log n)\) space and read in \(\mathcal{O}(n\log\sigma/\log n)\) time. We show that we can compute an LCS of two strings in time \(\mathcal{O}(n\log\sigma/\sqrt{\log n})\) in the word RAM model, which is sublinear in \( n \) if \(\sigma=2^{o(\sqrt{\log n})}\) (in particular, if \(\sigma=\mathcal{O}(1)\) ), using optimal space \(\mathcal{O}(n\log\sigma/\log n)\) . In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. The same complexity can be achieved for computing an LCS of \(\lambda=\mathcal{O}(\sqrt{\log n}/\log\log n)\) input strings of total length \( n \) . We then lift our ideas to the problem of computing a \( k \) -mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of \( S \) that occurs in \( T \) with at most \( k \) mismatches. Flouri et al. showed how to compute a 1-mismatch LCS in \(\mathcal{O}(n\log n)\) time [IPL 2015]. Thankachan et al. extended this result to computing a \( k \) -mismatch LCS in \(\mathcal{O}(n\log^{k}n)\) time for \(k=\mathcal{O}(1)\) [J. Comput. Biol. 2016]. We show an \(\mathcal{O}(n\log^{k-0.5}n)\) -time algorithm, for any constant integer \(k > 0\) and irrespective of the alphabet size, using \(\mathcal{O}(n)\) space as the previous approaches. We thus notably break through the well-known \(n\log^{k}n\) barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. for string indexing with \( k \) errors [STOC 2004]. As a by-product, we improve upon the algorithm of Charalampopoulos et al. [CPM 2018] for computing a \( k \) -mismatch LCS in the case when the output \( k \) -mismatch LCS is sufficiently long.

    Cited by 5
  • Website
    Google Scholar

    Internal quasiperiod queries

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

  • Website
    Google Scholar
    Open Access

    Space-Efficient k-Mismatch Text Indexes

    by Tomasz Kociumaka, Jakub Radoszewski

    A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length $n$) into an efficient index (a data structure) supporting queries about the text. Cole, Gottlieb, and Lewenstein (STOC 2004) proposed $k$-errata trees, a family of text indexes supporting approximate pattern matching queries of several types. In particular, $k$-errata trees yield an elegant solution to $k$-mismatch queries, where we are to report all substrings of the text with Hamming distance at most $k$ to the query pattern. The resulting $k$-mismatch index uses $O(n\log^k n)$ space and answers a query for a length-$m$ pattern in $O(\log^k n \log \log n + m + occ)$ time, where $occ$ is the number of approximate occurrences. In retrospect, $k$-errata trees appear very well optimized: even though a large body of work has adapted $k$-errata trees to various settings throughout the past two decades, the original time-space trade-off for $k$-mismatch indexing has not been improved in the general case. We present the first such improvement, a $k$-mismatch index with $O(n\log^{k-1} n)$ space and the same query time as $k$-errata trees. Previously, due to a result of Chan, Lam, Sung, Tam, and Wong (Algorithmica 2010), such an $O(n\log^{k-1} n)$-size index has been known only for texts over alphabets of constant size. In this setting, however, we obtain an even smaller $k$-mismatch index of size only $O(n \log^{k-2+\varepsilon+\frac{2}{k+2-(k \bmod 2)}} n)\subseteq O(n\log^{k-1.5+\varepsilon} n)$ for $2\le k\le O(1)$ and any constant $\varepsilon>0$. Along the way, we also develop improved indexes for short patterns, offering better trade-offs in this practically relevant special case.

  • Website
    Google Scholar
    Open Access

    Subsequence covers of words

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

  • Website
    Google Scholar
    Open Access

    Elastic-degenerate string comparison

    by Estéban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, Wiktor Zuba

    Cited by 4
  • Website
    Google Scholar

    Internal Pattern Matching Queries in a Text and Applications

    by Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

    We consider several types of internal queries, that is, questions about fragments of a given text [Formula: see text] specified in constant space by their locations in [Formula: see text]. Our main result is an optimal data structure for internal pattern matching (IPM) queries, which, given two fragments [Formula: see text] and [Formula: see text], ask for a representation of all fragments contained in [Formula: see text] and matching [Formula: see text] exactly. This problem can be viewed as an internal version of the fundamental exact pattern matching problem: We are looking for exact occurrences of one substring of [Formula: see text] within another substring of [Formula: see text]. Our data structure answers IPM queries in time proportional to the quotient [Formula: see text] of the fragments’ lengths, which is required due to the worst-case information content of the output. If [Formula: see text] is a text of length [Formula: see text] over an integer alphabet of size [Formula: see text], then our data structure occupies [Formula: see text] machine words (that is, [Formula: see text] bits) and admits an [Formula: see text]-time construction algorithm. We also show how to use IPM queries for answering internal queries corresponding to other classic string processing problems. Among others, we derive optimal data structures reporting the periods of a fragment and testing the cyclic equivalence of two fragments. Since the publication of the conference version of this paper [Kociumaka et al., Internal pattern matching queries in a text and applications, SODA 2015], IPM queries have found numerous further applications, following the path paved by the classic longest common extension (LCE) queries of Landau and Vishkin [ J. Comput. System Sci., 37 (1988), pp. 63–78]. In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the [Formula: see text] model, developed by Charalampopoulos, Kociumaka, and Wellnitz [ Faster approximate pattern matching: A unified approach, FOCS 2020] to design approximate pattern matching algorithms that work in multiple settings. All our algorithms are deterministic, whereas the data structure in the conference version of the paper only admits a randomized construction in [Formula: see text] expected time. To achieve this, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka [ String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure, STOC 2019]. Our method, based on a new restricted version of the recompression technique of Jeż [ J. ACM, 63 (2016), pp. 4:1–4:51], yields a hierarchy of [Formula: see text] string synchronizing sets covering the whole spectrum of the fragments’ lengths.

    Cited by 26
Show all