Transposition invariant string matching

DOI10.1016/j.jalgor.2004.07.008zbMath1083.68030OpenAlexW2073544604MaRDI QIDQ5692274

Veli Mäkinen, Esko Ukkonen, Gonzalo Navarro

Publication date: 28 September 2005

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

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.07.008

zbMATH Keywords

Edit distanceMusic sequence comparisonRange-minimum searchingSparse dynamic programmingTransposition invariance

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items (10)

Rotation and lighting invariant template matching ⋮ Speeding up transposition-invariant string matching ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Space-efficient data-analysis queries on grids ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME ⋮ Sequential and indexed two-dimensional combinatorial template matching allowing rotations

This page was built for publication: Transposition invariant string matching