Faster Online Elastic Degenerate String Matching

DOI10.4230/LIPIcs.CPM.2018.9zbMath1497.68590OpenAlexW2804695551MaRDI QIDQ5140772

Hideo Bannai, Yuto Nakashima, Kotaro Aoyama, Masayuki Takeda, Shunsuke Inenaga, Tomohiro I.

Publication date: 16 December 2020

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2018.9

zbMATH Keywords

Boolean convolutionelastic degenerate pattern matching

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, Algorithms and complexity on indexing founder graphs, Elastic-degenerate string matching with 1 error, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, Unnamed Item, Efficient pattern matching in elastic-degenerate strings, Approximate pattern matching on elastic-degenerate text, Comparing Degenerate Strings, Elastic-Degenerate String Matching via Fast Matrix Multiplication

Cites Work

• Unnamed Item
• Optimal on-line decremental connectivity in trees
• Efficient pattern matching in elastic-degenerate strings
• Generalized String Matching
• Fast Pattern Matching in Strings
• On-line pattern matching on similar texts
• Pattern Matching on Elastic-Degenerate Text with Errors
• An Algorithm for the Machine Calculation of Complex Fourier Series