Semi-local longest common subsequences in subquadratic time

DOI10.1016/j.jda.2008.07.001zbMath1154.68543OpenAlexW2066688636MaRDI QIDQ1002102

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

string algorithmslongest common subsequencesemi-local string comparison

Mathematics Subject Classification ID

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

Related Items (13)

A substring-substring LCS data structure ⋮ Faster subsequence recognition in compressed strings ⋮ A fast algorithm for multiplying min-sum permutations ⋮ Monge properties of sequence alignment ⋮ An almost quadratic time algorithm for sparse spliced alignment ⋮ Efficient all path score computations on grid graphs ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ On almost Monge all scores matrices ⋮ Unnamed Item ⋮ Periodic String Comparison ⋮ Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence ⋮ Fast distance multiplication of unit-Monge matrices ⋮ A data structure for substring-substring LCS length queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• A dynamic edit distance table
• A faster algorithm computing string edit distances
• Perspectives of Monge properties in optimization
• On the Common Substring Alignment Problem
• All Semi-local Longest Common Subsequences in Subquadratic Time
• Bounds on the Complexity of 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
• Incremental String Comparison
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Combinatorial Pattern Matching
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

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