Source author record

Juliusz Straszyński

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Circular Pattern Matching with $k$ Mismatches

The $k$ -mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length- $m$ substring of a text $T$ of length $n$ , if this distance is no more than $k$ . In many real-world applications, any cyclic rotation of $P$ is a relevant pattern, and thus one is interested in computing the minimal distance of every length- $m$ substring of $T$ and any cyclic rotation of $P$ . This is the circular pattern matching with $k$ mismatches ( $k$ -CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the $k$ -CPM problem. Specifically, we show an $O(nk)$ -time algorithm and an $O(n+\frac{n}{m}\,k^4)$ -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the $k$ -mismatch problem [Bringmann et al., SODA 2019]. A preliminary version of this work appeared at FCT 2019. In this version we improve the time complexity of the main algorithm from $O(n+\frac{n}{m}\,k^5)$ to $O(n+\frac{n}{m}\,k^4)$ .

preprint2020arXiv

Counting Distinct Patterns in Internal Dictionary Matching

We consider the problem of preprocessing a text $T$ of length $n$ and a dictionary $\mathcal{D}$ in order to be able to efficiently answer queries $CountDistinct(i,j)$ , that is, given $i$ and $j$ return the number of patterns from $\mathcal{D}$ that occur in the fragment $T[i \mathinner{.\,.} j]$ . The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$ . This way, the dictionary takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $Θ(n\cdot d)$ . An $\tilde{\mathcal{O}}(n+d)$ -size data structure that answers $CountDistinct(i,j)$ queries $\mathcal{O}(\log n)$ -approximately in $\tilde{\mathcal{O}}(1)$ time was recently proposed in a work that introduced internal dictionary matching [ISAAC 2019]. Here we present an $\tilde{\mathcal{O}}(n+d)$ -size data structure that answers $CountDistinct(i,j)$ queries $2$ -approximately in $\tilde{\mathcal{O}}(1)$ time. Using range queries, for any $m$ , we give an $\tilde{\mathcal{O}}(\min(nd/m,n^2/m^2)+d)$ -size data structure that answers $CountDistinct(i,j)$ queries exactly in $\tilde{\mathcal{O}}(m)$ time. We also consider the special case when the dictionary consists of all square factors of the string. We design an $\mathcal{O}(n \log^2 n)$ -size data structure that allows us to count distinct squares in a text fragment $T[i \mathinner{.\,.} j]$ in $\mathcal{O}(\log n)$ time.

preprint2020arXiv

Efficient Representation and Counting of Antipower Factors in Words

A $k$ -antipower (for $k \ge 2$ ) is a concatenation of $k$ pairwise distinct words of the same length. The study of fragments of a word being antipowers was initiated by Fici et al. (ICALP 2016) and first algorithms for computing such fragments were presented by Badkobeh et al. (Inf. Process. Lett., 2018). We address two open problems posed by Badkobeh et al. We propose efficient algorithms for counting and reporting fragments of a word which are $k$ -antipowers. They work in $\mathcal{O}(nk \log k)$ time and $\mathcal{O}(nk \log k + C)$ time, respectively, where $C$ is the number of reported fragments. For $k=o(\sqrt{n/\log n})$ , this improves the time complexity of $\mathcal{O}(n^2/k)$ of the solution by Badkobeh et al. We also show that the number of different $k$ -antipower factors of a word of length $n$ can be computed in $\mathcal{O}(nk^4 \log k \log n)$ time. Our main algorithmic tools are runs and gapped repeats. Finally we present an improved data structure that checks, for a given fragment of a word and an integer $k$ , if the fragment is a $k$ -antipower. This is a full and extended version of a paper from LATA 2019. In particular, all results about counting different antipowers factors are completely new compared with the LATA proceedings version.

preprint2020arXiv

Internal Quasiperiod Queries

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 (for the first time) internal queries asking for covers (also known as quasiperiods) of a given factor. We propose a data structure that answers such queries in $O(\log n \log \log n)$ time for the shortest cover and in $O(\log n (\log \log n)^2)$ time for a representation of all the covers, after $O(n \log n)$ time and space preprocessing.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Juliusz Straszyński

Research overview

Is this your work?

4 publications

Circular Pattern Matching with $k$ Mismatches

Counting Distinct Patterns in Internal Dictionary Matching

Efficient Representation and Counting of Antipower Factors in Words

Internal Quasiperiod Queries

See the researcher in context

Building this map preview

Juliusz Straszyński

Research overview

Is this your work?

4 publications

Circular Pattern Matching with kkk Mismatches

Counting Distinct Patterns in Internal Dictionary Matching

Efficient Representation and Counting of Antipower Factors in Words

Internal Quasiperiod Queries

See the researcher in context

Building this map preview

Circular Pattern Matching with $k$ Mismatches