A substring-substring LCS data structure
From MaRDI portal
Recommendations
- A data structure for substring-substring LCS length queries
- Sublinear space algorithms for the longest common substring problem
- scientific article; zbMATH DE number 1263248
- Computing Longest Common Substrings Via Suffix Arrays
- A bit-string longest-common-subsequence algorithm
- A family of fast constant-space substring search algorithms
- Space-efficient STR-IC-LCS computation
- Position-Restricted Substring Searching
- Linear time algorithms for generalizations of the longest common substring problem
- Time-space trade-offs for the longest common substring problem
Cites work
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- A fast algorithm for multiplying min-sum permutations
- Algorithms for the Longest Common Subsequence Problem
- Algorithms on Strings, Trees and Sequences
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- An almost quadratic time algorithm for sparse spliced alignment
- Better tradeoffs for exact distance oracles in planar graphs
- Efficient all path score computations on grid graphs
- Exact distance oracles for planar graphs
- Fast distance multiplication of unit-Monge matrices
- Many distances in planar graphs
- Multiple-source shortest paths in planar graphs
- On compact representations of all-pairs-shortest-path-distance matrices
- On the complexity of \(k\)-SAT
- Semi-local longest common subsequences in subquadratic time
- Short path queries in planar graphs in constant time
- Shortest path queries in planar graphs
- The String-to-String Correction Problem
- Which problems have strongly exponential complexity?
Cited in
(5)- A data structure for substring-substring LCS length queries
- Two-dimensional substring indexing.
- Internal shortest absent word queries in constant time and linear space
- A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
- scientific article; zbMATH DE number 7765364 (Why is no real title available?)
This page was built for publication: A substring-substring LCS data structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1625599)