A substring-substring LCS data structure

DOI10.1016/j.tcs.2018.06.034zbMath1407.68579OpenAlexW2810044314WikidataQ129597380 ScholiaQ129597380MaRDI QIDQ1625599

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 pathstring algorithmslongest common subsequencesemi-local string comparison

Mathematics Subject Classification ID

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

Related Items (5)

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 ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Unnamed Item ⋮ A data structure for substring-substring LCS length queries

Cites Work

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

This page was built for publication: A substring-substring LCS data structure