Semi-local longest common subsequences in subquadratic time

DOI10.1016/J.JDA.2008.07.001zbMATH Open1154.68543OpenAlexW2066688636MaRDI QIDQ1002102FDOQ1002102

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

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

zbMATH Keywords

longest common subsequencestring algorithmssemi-local string comparison

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

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

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)