1 citations · 1 across the 1 of their papers we have counts for
5 papers
Hardness of Detecting Abelian and Additive Square Factors in Strings
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński +2
We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in…
Internal Quasiperiod Queries
Maxime Crochemore, Costas Iliopoulos, Jakub Radoszewski +4
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 g…
The Number of Repetitions in 2D-Strings
Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter +2
The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-…
Counting Distinct Patterns in Internal Dictionary Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed +5
We consider the problem of preprocessing a text of length and a dictionary in order to be able to efficiently answer queries , that is, gi…
Fast Algorithm for Partial Covers in Words
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter +2
A factor of a word is a cover of if every position in lies within some occurrence of in . A word covered by thus generalizes the idea of a repetition…