Semi-local string comparison: algorithmic techniques and applications

DOI10.1007/S11786-007-0033-3MaRDI QIDQ942990zbMATH OpenOpenAlexFDO

Authors Alexander Tiskin

Publication date 8 September 2008

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-007-0033-3

zbMATH Keywords

longest common subsequencesemi-local string comparisonstring algorithms

Mathematics Subject Classification ID

Combinatorics on words (68R15) Nonnumerical algorithms (68W05)

Recommendations

• Semi-local longest common subsequences in subquadratic time
• All Semi-local Longest Common Subsequences in Subquadratic Time
• The longest common subsequence problem revisited
• An all-substrings common subsequence algorithm
• A fast longest common subsequence algorithm for similar strings

Cited in

(32)

• Semi-local longest common subsequences in subquadratic time
• On almost Monge all scores matrices
• Comparison of strings belonging to the same family
• Longest common rollercoasters
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• Fast distance multiplication of unit-Monge matrices
• An almost quadratic time algorithm for sparse spliced alignment
• Efficient all path score computations on grid graphs
• Internal shortest absent word queries in constant time and linear space
• Towards approximate matching in compressed strings: local subsequence recognition
• String comparison by transposition networks
• 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
• Dynamic edit distance table under a general weighted cost function
• Local search for string problems: brute force is essentially optimal
• Near-optimal distance emulator for planar graphs
• Bounded-length Smith-Waterman alignment
• scientific article; zbMATH DE number 7765364 (Why is no real title available?)
• Longest bordered and periodic subsequences
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Approximate circular pattern matching
• Streaming and small space approximation algorithms for edit distance and longest common subsequence
• Many flavors of edit distance
• Doubly-periodic string comparison
• Edit distance in near-linear time: it's a constant factor
• Bounded weighted edit distance: dynamic algorithms and matching lower bounds
• Core-sparse Monge matrix multiplication: improved algorithm and applications
• Faster subsequence recognition in compressed strings
• An algorithm for solving the longest increasing circular subsequence problem

This page was built for publication: Semi-local string comparison: algorithmic techniques and applications

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