2026-07-20T05:59:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8701 2024-03-06T10:43:01Z ddc:004 open_access

Faster Online Elastic Degenerate String Matching Aoyama, Kotaro Nakashima, Yuto I, Tomohiro Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki elastic degenerate pattern matching boolean convolution An Elastic-Degenerate String [Iliopoulus et al., LATA 2017] is a sequence of sets of strings, which was recently proposed as a way to model a set of similar sequences. We give an online algorithm for the Elastic-Degenerate String Matching (EDSM) problem that runs in O(nm sqrt{m log m} + N) time and O(m) working space, where n is the number of elastic degenerate segments of the text, N is the total length of all strings in the text, and m is the length of the pattern. This improves the previous algorithm by Grossi et al. [CPM 2017] that runs in O(nm^2 + N) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kotaro Aoyama and Yuto Nakashima and Tomohiro I and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.9 urn:nbn:de:0030-drops-87016 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode