P. Charalampopoulos

Text Indexing: From Reporting to Counting

Ben Bals, Panagiotis Charalampopoulos, Oded Lachish +2

We prove an elementary yet powerful combinatorial lemma: in any rooted tree with $L$ leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is…

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 $S$ of length $n$ . Both pro…

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms

Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert +2

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorit…

Approximate Cartesian Tree Matching with Substitutions

Panagiotis Charalampopoulos, Jonas Ellert, Manal Mohamed

The Cartesian tree of a sequence captures the relative order of the sequence's elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly…

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…

Pattern Matching under Weighted Edit Distance

Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz

In Pattern Matching with Weighted Edits (PMWED), we are given a pattern $P$ of length $m$ , a text $T$ of length $n$ , a positive threshold $k$ , and oracle access to a weight functio…

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 $C$ is an s-cover of a word $S$ if the occurrences of $C$ in $S$ 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 $n$ over an alphabet of size $σ$ can be computed in $O (n / lo g_{σ} n)$ time in the word-RAM model. This paper i…

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 $S$ of length $n$ that occur at least $τ$ …

Longest Common Extensions with Wildcards: Trade-off and Applications

Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos +2

We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other c…

Internal Pattern Matching in Small Space and Applications

Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya

In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our mai…

Optimal Bounds for Distinct Quartics

Panagiotis Charalampopoulos, Paweł Gawrychowski, Samah Ghazawi

A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the…

Approximate Circular Pattern Matching under Edit Distance

Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3

In the $k$ -Edit Circular Pattern Matching ( $k$ -Edit CPM) problem, we are given a length- $n$ text $T$ , a length- $m$ pattern $P$ , and a positive integer threshold $k$ , and we are to…