A data structure for substring-substring LCS length queries

DOI10.1016/J.TCS.2022.02.004MaRDI QIDQ2118872OpenAlexFDO

Authors 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)

Recommendations

• An all-substrings common subsequence algorithm
• Semi-local longest common subsequences in subquadratic time
• All Semi-local Longest Common Subsequences in Subquadratic Time
• A substring-substring LCS data structure
• A fast longest common subsequence algorithm for similar strings

Cites work

• scientific article; zbMATH DE number 30301 (Why is no real title available?)
• scientific article; zbMATH DE number 7765364 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• A fast algorithm for computing longest common subsequences
• A fast algorithm for multiplying min-sum permutations
• A faster algorithm computing string edit distances
• A linear-time algorithm for a special case of disjoint set union
• A longest common subsequence algorithm suitable for similar text strings
• A new efficient algorithm for computing the longest common subsequence
• A simple algorithm for the constrained sequence problems
• A substring-substring LCS data structure
• An almost quadratic time algorithm for sparse spliced alignment
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Fast distance multiplication of unit-Monge matrices
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• On the common substring alignment problem
• On the generalized constrained longest common subsequence problems
• Semi-local longest common subsequences in subquadratic time
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited

Cited in

(3)

• Two-dimensional substring indexing.
• A substring-substring LCS data structure
• Internal shortest absent word queries in constant time and linear space

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118872)