36 citations · 92 across the 24 of their papers we have counts for
40 papers
Subsequence Covers of Words
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3
We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word is an s-cover of a word if the occurrences of in as subsequences cover…
Counting Distinct Square Substrings in Sublinear Time
Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski +3
We show that the number of distinct squares in a packed string of length over an alphabet of size can be computed in time in the word-RAM model. This paper i…
Approximate Circular Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3
In the -Edit Circular Pattern Matching (-Edit CPM) problem, we are given a length- text , a length- pattern , and a positive integer threshold , and we are to…
Approximate Circular Pattern Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +4
We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length- text , a length- pattern , and a…
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…
Tight Bound for the Number of Distinct Palindromes in a Tree
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1
For an undirected tree with edges labelled by single letters, we consider its substrings, which are labels of the simple paths between pairs of nodes. We prove that there are $…