An almost optimal edit distance oracle
From MaRDI portal
Cites work
- A substring-substring LCS data structure
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Almost optimal distance oracles for planar graphs
- Better tradeoffs for exact distance oracles in planar graphs
- Computing minimal and maximal suffixes of a substring
- Conditional lower bounds for space/time tradeoffs
- Counting distinct patterns in internal dictionary matching
- Counting palindromes in substrings
- Decomposable searching problems
- Distance oracles beyond the Thorup-Zwick bound
- Dynamic and internal longest common substring
- Dynamic String Alignment.
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast and compact exact distance oracle for planar graphs
- Fast parallel and serial approximate string matching
- Faster approximate pattern matching: a unified approach
- Generalized substring compression
- scientific article; zbMATH DE number 7788487 (Why is no real title available?)
- Internal dictionary matching
- Internal pattern matching queries in a text and applications
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Minimal suffix and rotation of a substring in optimal time
- Multiple-source shortest paths in embedded graphs
- Multiple-source shortest paths in planar graphs
- Near-optimal compression for the planar graph metric
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Preserving order in a forest in less than logarithmic time and linear space
- Quadratic conditional lower bounds for string problems and dynamic time warping
- Semi-local longest common subsequences in subquadratic time
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Tight hardness results for LCS and other sequence similarity measures
- Wavelet trees meet suffix trees
Cited in
(2)
This page was built for publication: An almost optimal edit distance oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241146)
