A data structure for substring-substring LCS length queries

DOI10.1016/j.tcs.2022.02.004OpenAlexW4212888132MaRDI QIDQ2118872

Yoshifumi Sakai

Publication date: 23 March 2022

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

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

zbMATH Keywords

algorithmslongest common subsequencesemi-local string comparison

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Internal shortest absent word queries in constant time and linear space ⋮ Finding top-\(k\) longest palindromes in substrings

Cites Work

• Unnamed Item
• Unnamed Item
• A fast algorithm for multiplying min-sum permutations
• On the generalized constrained longest common subsequence problems
• A new efficient algorithm for computing the longest common subsequence
• Semi-local longest common subsequences in subquadratic time
• The constrained longest common subsequence problem
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• A linear-time algorithm for a special case of disjoint set union
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• A substring-substring LCS data structure
• Fast distance multiplication of unit-Monge matrices
• A simple algorithm for the constrained sequence problems
• An almost quadratic time algorithm for sparse spliced alignment
• On the Common Substring Alignment Problem
• A fast algorithm for computing longest common subsequences
• The String-to-String Correction Problem
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching

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