Elastic-Degenerate String Matching via Fast Matrix Multiplication
DOI10.1137/20M1368033OpenAlexW3158236668WikidataQ114074153 ScholiaQ114074153MaRDI QIDQ5864665
Paweł Gawrychowski, Giulia Bernardini, Solon P. Pissis, Nadia Pisanti, Giovanna Rosone
Publication date: 8 June 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.02298
fast Fourier transformpattern matchingstring algorithmsmatrix multiplicationelastic-degenerate string
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01) Algorithms on strings (68W32)
Related Items (1)
Uses Software
Cites Work
- Simple deterministic wildcard matching
- Fast pattern-matching on indeterminate strings
- Lossless filter for multiple repetitions with Hamming distance
- Computing dominances in \(E^ n\)
- General context-free recognition in less than cubic time
- An improved combinatorial algorithm for Boolean matrix multiplication
- A data structure for dynamic trees
- Efficient pattern matching in elastic-degenerate strings
- Approximate pattern matching on elastic-degenerate text
- On hardness of several string indexing problems
- Efficient determination of the transitive closure of a directed graph
- NR‐grep: a fast and flexible pattern‐matching tool
- Finding a maximum weight triangle in n 3-Δ time, with applications
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Factorizing words over an ordered alphabet
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Constructing Efficient Dictionaries in Close to Sorting Time
- Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
- Verifying candidate matches in sparse and wildcard matching
- The Complexity of Satisfiability of Small Depth Circuits
- Generalized String Matching
- Multidimensional binary search trees used for associative searching
- Fast Pattern Matching in Strings
- Finding a Minimum Circuit in a Graph
- Two-way string-matching
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
- Faster algorithms for string matching with k mismatches
- Comparing Degenerate Strings
- Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
- On-line pattern matching on similar texts
- Faster Online Elastic Degenerate String Matching
- Pattern Matching on Elastic-Degenerate Text with Errors
- Regularity Lemmas and Combinatorial Algorithms
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Uniqueness Theorems for Periodic Functions
- Internal Pattern Matching Queries in a Text and Applications
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Hardness of RNA Folding Problem With Four Symbols.
- Color-Distance Oracles and Snippets
- Multiplying matrices faster than coppersmith-winograd
- Algorithms on Strings
- Algorithms – ESA 2004
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Elastic-Degenerate String Matching via Fast Matrix Multiplication
