5 papers · 1 filter
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…