8 papers
Faster Algorithms for Shortest Unique or Absent Substrings
Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis +2
We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) of a string of length . Both pro…
Variations on the Problem of Identifying Spectrum-Preserving String Sets
Sankardeep Chakraborty, Roberto Grossi, Ren Kimura +3
In computational genomics, many analyses rely on efficient storage and traversal of -mers, motivating compact representations such as spectrum-preserving string sets (SPSS), whi…
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…
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…
Minimizers in Semi-Dynamic Strings
Wiktor Zuba, Oded Lachish, Solon P. Pissis
Minimizers sampling is one of the most widely-used mechanisms for sampling strings. Let be a string over an alphabet . In addition, let and $k\g…