Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics

DOI10.1007/s00453-009-9345-9zbMath1215.68282OpenAlexW1974523510MaRDI QIDQ534777

Ohad Lipsky, Ely Porat

Publication date: 10 May 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9345-9

zbMATH Keywords

Hamming distanceapproximate string matchingcombinatorial algorithms on wordsdesign and analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items

Closest periodic vectors in \(L_p\) spaces, Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance, Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances, Hamming Distance Completeness, Approximating Approximate Pattern Matching, Recent advances in text-to-pattern distance algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm computing string edit distances
• Fast algorithms for approximately counting mismatches
• Alphabet dependence in parameterized matching
• Efficient 2-dimensional approximate matching of half-rectangular figures
• String matching under a general matching relation
• Verifying candidate matches in sparse and wildcard matching
• Generalized String Matching
• Fast Pattern Matching in Strings
• Faster algorithms for string matching with k mismatches
• A theory of parameterized pattern matching
• Automata, Languages and Programming
• A randomized algorithm for approximate string matching