29 citations · 45 across the 41 of their papers we have counts for
12 papers · 1 filter
Maximal Palindromes in MPC: Simple and Optimal
Solon P. Pissis
In the classical longest palindromic substring (LPS) problem, we are given a string of length , and the task is to output a longest palindromic substring in . Gilbert, Ha…
Subtree Mode and Applications
Jialong Zhou, Ben Bals, Matei Tinca +4
The mode of a collection of values (i.e., the most frequent value in the collection) is a key summary statistic. Finding the mode in a given range of an array of values is thus of…
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…
When is String Reconstruction using de Bruijn Graphs Hard?
Ben Bals, Sebastiaan van Krieken, Solon P. Pissis +2
The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly…
Testing Quasiperiodicity
Christine Awofeso, Ben Bals, Oded Lachish +1
A cover (or quasiperiod) of a string is a shorter string such that every position of is contained in some occurrence of as a substring. The notion of covers was int…
Text Indexing and Pattern Matching with Ephemeral Edits
Solon P. Pissis
A sequence of edit operations in a string is called ephemeral if operation constructing string , for all with , is reverted b…
Contextual Pattern Mining and Counting
Ling Li, Daniel Gibney, Sharma V. Thankachan +2
Given a string of length , a longer string of length , and two integers and , the context of in is the set of all string pairs , w…
Resilient Pattern Mining
Pengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad +3
Frequent pattern mining is a flagship problem in data mining. In its most basic form, it asks for the set of substrings of a given string of length that occur at least …
Indexing Strings with Utilities
Giulia Bernardini, Huiping Chen, Alessio Conte +5
Applications in domains ranging from bioinformatics to advertising feature strings that come with numerical scores (utilities). The utilities quantify the importance, interest, pro…
Faster ED-String Matching with Mismatches
Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak +2
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compac…
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\ge…
U-index: A Universal Indexing Framework for Matching Long Patterns
Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp +4
Text indexing is a fundamental and well-studied problem. Classic solutions either replace the original text with a compressed representation, e.g., the FM-index and its variants, o…