Abstract
The Elastic Degenerate String Matching (EDSM) problem is defined as that of finding an occurrence of a pattern P of length m in an EDtext T. A Dtext (Degenerate text) is a string that actually represents a set of similar and aligned strings (e.g. a pangenome [The Computational PanGenomics Consortium, 2018]) by collapsing common fragments into a standard string, and representing variants with sets of alternative substrings. When such substrings are not bound to have the same size, then we talk about elastic Dstrings (EDstrings). In [R.Grossi et al., 2017] we gave an O(nm²+N) time online algorithm for EDSM, where n is the length of T and N is its size, defined as the total number of letters. A fundamental toolkit of our algorithm is the O(m²+N) time solution of the later called Active Prefixes problem (AP). In [K.Aoyama et al., 2018], a O(m^{1.5} √{log m}+N) solution for AP was shown, leading to a O(nm^{1.5} √{log m}+N) time solution for EDSM. The natural open problem was thus whether the 1.5 exponent could furtherly be decreased. In [G.Bernardini et al., 2019], we prove several properties that answer this and other questions: we give a conditional O(nm^{1.5}+N) lower bound for EDSM, proving that a combinatorial algorithm solving EDSM in O(nm^{1.5ε} +N) time would break the Boolean Matrix Multiplication (BMM) conjecture; we use this result as a hint to devise a noncombinatorial algorithm that solves EDSM in O(nm^{1.381}+N) time; we do so by successfully combining Fast Fourier Transform and properties of string periodicity. In my talk I will overview the results above, as well as some interesting side results: the extension to a dictionary rather than a single pattern [S.P.Pissis and A.Retha, 2018], the introduction of errors [G.Bernardini et al., 2020], and a notion of matching among Dstrings with its linear time solution [M.Alzamel et al., 2020].
BibTeX  Entry
@InProceedings{pisanti:LIPIcs.CPM.2021.3,
author = {Pisanti, Nadia},
title = {{OnLine Pattern Matching on DTexts}},
booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
pages = {3:13:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771863},
ISSN = {18688969},
year = {2021},
volume = {191},
editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13954},
URN = {urn:nbn:de:0030drops139548},
doi = {10.4230/LIPIcs.CPM.2021.3},
annote = {Keywords: pattern matching, elasticdegenerate string, matrix multiplication}
}
Keywords: 

pattern matching, elasticdegenerate string, matrix multiplication 
Collection: 

32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) 
Issue Date: 

2021 
Date of publication: 

30.06.2021 