Faster Online Elastic Degenerate String Matching

DOI10.4230/LIPICS.CPM.2018.9MaRDI QIDQ5140772zbMATH OpenOpenAlexFDO

Authors Kotaro Aoyama, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, 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)

Recommendations

• Even faster elastic-degenerate string matching via fast matrix multiplication
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Faster approximate string matching
• On-line approximate string matching with bounded errors
• On-Line Approximate String Matching with Bounded Errors
• Fast and practical approximate string matching
• Faster filters for approximate string matching
• A fast suffix automata based algorithm for exact online string matching

Cites work

• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Fast Pattern Matching in Strings
• Generalized String Matching
• On-line pattern matching on similar texts
• Optimal on-line decremental connectivity in trees
• Pattern matching on elastic-degenerate text with errors

Cited in

(15)

• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Approximate pattern matching on elastic-degenerate text
• scientific article; zbMATH DE number 7286689 (Why is no real title available?)
• An Efficient Elastic-Degenerate Text Index? Not Likely
• Comparing Degenerate Strings
• Degenerate string comparison and applications
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Algorithms and complexity on indexing founder graphs
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Elastic-degenerate string matching with 1 error
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Elastic-degenerate string matching with 1 error or mismatch
• An artificial neural network based approach for online string matching/filtering of large databases
• Pattern matching on elastic-degenerate text with errors
• IDPM: an improved degenerate pattern matching algorithm for biological sequences

This page was built for publication: Faster Online Elastic Degenerate String Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140772)