Zobrazeno 1 - 10
of 119
pro vyhledávání: '"CHARALAMPOPOULOS, PANAGIOTIS"'
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 character in the alphabet, similar to the character "?" in Unix command
Externí odkaz:
http://arxiv.org/abs/2408.03610
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 main contribution is a space-time trade-off for the Internal Pattern Matc
Externí odkaz:
http://arxiv.org/abs/2404.17502
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 most basic questions is how many distinct squares, i.e., distinct str
Externí odkaz:
http://arxiv.org/abs/2403.06667
Autor:
Charalampopoulos, Panagiotis, Pissis, Solon P., Radoszewski, Jakub, Rytter, Wojciech, Waleń, Tomasz, Zuba, Wiktor
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 report all starting positions of the substrings of $T$ that are at edi
Externí odkaz:
http://arxiv.org/abs/2402.14550
In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern $P$ of length $m$ containing $D$ wildcards, a text $T$ of length $n$, and an integer $k$, our objective is to identify all fragments of $T$ within Ha
Externí odkaz:
http://arxiv.org/abs/2402.07732
We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. Let $T_1$ and $T_2$ be two rooted trees whose nodes have weights that a
Externí odkaz:
http://arxiv.org/abs/2302.01373
Autor:
Charalampopoulos, Panagiotis, Kociumaka, Tomasz, Radoszewski, Jakub, Pissis, Solon P., Rytter, Wojciech, Waleń, Tomasz, Zuba, Wiktor
We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a threshold $k>0$, and we are to report all starting positions of fragme
Externí odkaz:
http://arxiv.org/abs/2208.08915
We consider the approximate pattern matching problem under the edit distance. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to find the starting positions of all substrings of $T$ that can be transforme
Externí odkaz:
http://arxiv.org/abs/2204.03087
Autor:
CHARALAMPOPOULOS, PANAGIOTIS1 p.charalampopoulos@bbk.ac.uk, GAWRYCHOWSKI, PAWEŁ2 gawry@cs.uni.wroc.pl, YAOWEI LONG3 yaoweil@umich.edu, MOZES, SHAY4 smozes@runi.ac.il, PETTIE, SETH5 pettie@umich.edu, WEIMANN, OREN6 oren@cs.haifa.ac.il, WULFF-NILSEN, CHRISTIAN7 koolooz@di.ku.dk
Publikováno v:
Journal of the ACM. Apr2023, Vol. 70 Issue 2, p1-50. 50p.
Given a string $T$ of length $n$ over an alphabet $\Sigma\subset \{1,2,\ldots,n^{O(1)}\}$ of size $\sigma$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortest string over $\Sigma$ that is absent in th
Externí odkaz:
http://arxiv.org/abs/2106.01763