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

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

Cited in

(20)

• Approximate pattern matching on elastic-degenerate text
• An artificial neural network based approach for online string matching/filtering of large databases
• IDPM: an improved degenerate pattern matching algorithm for biological sequences
• Comparing Degenerate Strings
• Degenerate string comparison and applications
• Even faster elastic-degenerate string matching via fast matrix multiplication
• scientific article; zbMATH DE number 7286689 (Why is no real title available?)
• Pattern matching on elastic-degenerate text with errors
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• 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
• An Efficient Elastic-Degenerate Text Index? Not Likely
• Elastic-degenerate string matching with 1 error or mismatch
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching
• Elastic-degenerate string comparison
• Faster approximate elastic-degenerate string matching. Part A
• Faster approximate elastic-degenerate string matching. Part B
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

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)