8 papers
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…
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…
Syntactic View of Sigma-Tau Generation of Permutations
Wojciech Rytter, Wiktor Zuba
We give a syntactic view of the Sawada-Williams -generation of permutations. The corresponding sequence of -operations, of length is shown to be highly compressi…