On-line pattern matching on similar texts

DOI10.4230/LIPIcs.CPM.2017.9zbMath1434.68734OpenAlexW2617749016MaRDI QIDQ5110873

Giovanna Rosone, Nadia Pisanti, Costas S. Iliopoulos, Fatima Vayani, Chang Liu, Luca Versari, Solon P. Pissis, Roberto Grossi, Ahmad Retha

Publication date: 25 May 2020

Full work available at URL: https://doi.org/10.4230/lipics.cpm.2017.9

zbMATH Keywords

online algorithmspattern matchingstring algorithmsdegenerate stringselastic-degenerate strings

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Elastic-degenerate string matching with 1 error ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Pattern Matching on Elastic-Degenerate Text with Errors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient pattern matching in elastic-degenerate strings ⋮ Approximate pattern matching on elastic-degenerate text ⋮ Comparing Degenerate Strings ⋮ Unnamed Item ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Faster Online Elastic Degenerate String Matching