A substring-substring LCS data structure

DOI10.1016/J.TCS.2018.06.034MaRDI QIDQ1625599zbMATH OpenOpenAlexWikidataFDO

Authors Yoshifumi Sakai

Publication date 29 November 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.06.034

zbMATH Keywords

shortest pathlongest common subsequencestring algorithmssemi-local string comparison

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

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)