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 subsequencestring algorithmssemi-local string comparison

Mathematics Subject Classification ID

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

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

(24)

• String comparison by transposition networks
• Dynamic edit distance table under a general weighted cost function
• Fast distance multiplication of unit-Monge matrices
• Towards approximate matching in compressed strings: local subsequence recognition
• All Semi-local Longest Common Subsequences in Subquadratic Time
• An algorithm for solving the longest increasing circular subsequence problem
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Bounded-length Smith-Waterman alignment
• Monge properties of sequence alignment
• A fast algorithm for multiplying min-sum permutations
• Semi-local longest common subsequences in subquadratic time
• Longest bordered and periodic subsequences
• Local search for string problems: brute force is essentially optimal
• Near-optimal distance emulator for planar graphs
• Faster subsequence recognition in compressed strings
• An almost quadratic time algorithm for sparse spliced alignment
• Internal shortest absent word queries in constant time and linear space
• Efficient all path score computations on grid graphs
• Longest common rollercoasters
• On almost Monge all scores matrices
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Periodic String Comparison
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• scientific article; zbMATH DE number 7765364 (Why is no real title available?)

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)