36 citations · 62 across the 17 of their papers we have counts for
22 papers · 1 filter
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…
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 $…
Internal Dictionary Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed +3
We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary in fragments of a given string of length . The di…
Weighted Shortest Common Supersequence Problem Revisited
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis +5
A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSC…
Circular Pattern Matching with Mismatches
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis +5
The -mismatch problem consists in computing the Hamming distance between a pattern of length and every length- substring of a text of length , if this distance…
Quasi-Linear-Time Algorithm for Longest Common Circular Factor
Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos +6
We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings and of length , we are to compute the longest factor of whose cyclic shift occ…
Efficient Representation and Counting of Antipower Factors in Words
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter +3
A -antipower (for ) is a concatenation of pairwise distinct words of the same length. The study of fragments of a word being antipowers was initiated by Fici et al.…
Faster Recovery of Approximate Periods over Edit Distance
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter +3
The approximate period recovery problem asks to compute all of a given word of length : all primitive words () which have a pe…
Linear-Time Algorithm for Long LCF with Mismatches
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos +5
In the Longest Common Factor with Mismatches (LCF) problem, we are given two strings and of total length , and we are asked to find a pair of maximal-length fact…
String Periods in the Order-Preserving Model
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski +3
The order-preserving model (op-model, in short) was introduced quite recently but has already attracted significant attention because of its applications in data analysis. We intro…
Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +5
Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE que…
Faster Longest Common Extension Queries in Strings over General Alphabets
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1
Longest common extension queries (often called longest common prefix queries) constitute a fundamental building block in multiple string algorithms, for example computing runs and…
On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski +2
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings is sought containing as a factor ever…
Covering Problems for Partial Words and for Indeterminate Strings
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +3
We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of t…
On the String Consensus Problem and the Manhattan Sequence Consensus Problem
Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski +2
In the Manhattan Sequence Consensus problem (MSC problem) we are given integer sequences, each of length , and we are to find an integer sequence of length (called a…
A Note on the Longest Common Compatible Prefix Problem for Partial Words
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +6
For a partial word the longest common compatible prefix of two positions , denoted , is the largest such that , where $\uparr…
Internal Pattern Matching Queries in a Text and Applications
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter +1
We consider several types of internal queries, that is, questions about fragments of a given text specified in constant space by their locations in . Our main result is an o…
Order-Preserving Suffix Trees and Their Algorithmic Applications
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +6
Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for c…
A Note on Efficient Computation of All Abelian Periods in a String
Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka +6
We derive a simple efficient algorithm for Abelian periods knowing all Abelian squares in a string. An efficient algorithm for the latter problem was given by Cummings and Smyth in…
A Linear Time Algorithm for Seeds Computation
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski +2
A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. We show a linear-time algorithm computing a linear-size representat…
Efficient Seeds Computation Revisited
Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos +6
The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalizat…
On the maximal number of highly periodic runs in a string
Maxime Crochemore, Costas Iliopoulos, Marcin Kubica +3
A run is a maximal occurrence of a repetition with a period such that . The maximal number of runs in a string of length was studied by several authors and…