A substring-substring LCS data structure

DOI10.1016/J.TCS.2018.06.034zbMATH Open1407.68579OpenAlexW2810044314WikidataQ129597380 ScholiaQ129597380MaRDI QIDQ1625599FDOQ1625599

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

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

zbMATH Keywords

shortest pathlongest common subsequencestring algorithmssemi-local string comparison

Mathematics Subject Classification ID

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

Cites Work

• Algorithms on Strings, Trees and Sequences
• Title not available (Why is that?)
• Which problems have strongly exponential complexity?
• On the complexity of \(k\)-SAT
• The String-to-String Correction Problem
• Semi-local longest common subsequences in subquadratic time
• A fast algorithm for multiplying min-sum permutations
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms for the Longest Common Subsequence Problem
• Multiple-source shortest paths in planar graphs
• On compact representations of all-pairs-shortest-path-distance matrices
• An almost quadratic time algorithm for sparse spliced alignment
• Short path queries in planar graphs in constant time
• Better tradeoffs for exact distance oracles in planar graphs
• Many distances in planar graphs
• Fast distance multiplication of unit-Monge matrices
• Efficient all path score computations on grid graphs
• Shortest path queries in planar graphs
• Exact distance oracles for planar graphs

Cited In (5)

• A data structure for substring-substring LCS length queries
• Two-dimensional substring indexing.
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• Internal shortest absent word queries in constant time and linear space
• Title not available (Why is that?)

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)