Semi-local longest common subsequences in subquadratic time

DOI10.1016/J.JDA.2008.07.001MaRDI QIDQ1002102zbMATH OpenOpenAlexFDO

Authors Alexander Tiskin

Publication date 23 February 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.07.001

zbMATH Keywords

longest common subsequencesemi-local string comparisonstring algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• All Semi-local Longest Common Subsequences in Subquadratic Time
• Semi-local string comparison: algorithmic techniques and applications
• An all-substrings common subsequence algorithm
• The longest common subsequence problem revisited
• A fast longest common subsequence algorithm for similar strings

Cites work

• A dynamic edit distance table
• A faster algorithm computing string edit distances
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Algorithms on Strings, Trees and Sequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• All Semi-local Longest Common Subsequences in Subquadratic Time
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 5158495 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• Incremental String Comparison
• Multidimensional divide-and-conquer
• On the common substring alignment problem
• Perspectives of Monge properties in optimization
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

Cited in

(22)

• Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
• A substring-substring LCS data structure
• On almost Monge all scores matrices
• A data structure for substring-substring LCS length queries
• Fast distance multiplication of unit-Monge matrices
• An almost quadratic time algorithm for sparse spliced alignment
• Efficient all path score computations on grid graphs
• An all-substrings common subsequence algorithm
• Towards approximate matching in compressed strings: local subsequence recognition
• All Semi-local Longest Common Subsequences in Subquadratic Time
• Periodic String Comparison
• A fast algorithm for multiplying min-sum permutations
• Monge properties of sequence alignment
• Bounded-length Smith-Waterman alignment
• Computing longest common square subsequences
• Longest Square Subsequence Problem Revisited
• LCS approximation via embedding into locally non-repetitive strings
• An almost optimal edit distance oracle
• Doubly-periodic string comparison
• Core-sparse Monge matrix multiplication: improved algorithm and applications
• Faster subsequence recognition in compressed strings
• Semi-local string comparison: algorithmic techniques and applications

This page was built for publication: Semi-local longest common subsequences in subquadratic time

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