Longest common substring with approximately \(k\) mismatches

DOI10.1007/s00453-019-00548-xzbMath1412.68311arXiv1712.08573OpenAlexW2917954097MaRDI QIDQ2414870

Tatiana Starikovskaya, Tomasz Kociumaka, Jakub Radoszewski

Publication date: 17 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.08573

zbMATH Keywords

sketchinglongest common substringrandomised algorithmslocality-sensitive hashingbinary jumbled indexingstring similarity measures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (3)

Efficient computation of sequence mappability ⋮ Near-optimal quantum algorithms for string problems ⋮ Longest common substring made fully dynamic

Cites Work

• Unnamed Item
• Unnamed Item
• The longest common extension problem revisited and applications to approximate string searching
• Computing the longest common substring with one mismatch
• Efficient string matching with k mismatches
• Parallel string matching with k mismatches
• Which problems have strongly exponential complexity?
• PRIMES is in P
• A note on the longest common substring with \(k\)-mismatches problem
• Longest common substrings with \(k\) mismatches
• Time-space trade-offs for longest common extensions
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Longest Common Extensions via Fingerprinting
• Sublinear Space Algorithms for the Longest Common Substring Problem
• Clustered Integer 3SUM via Additive Combinatorics
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Fast Algorithms for Finding Nearest Common Ancestors
• Computing Longest Common Substrings Via Suffix Arrays
• Efficient algorithms for substring near neighbor problem
• Efficient randomized pattern-matching algorithms
• Algorithms on Strings, Trees and Sequences
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Time-Space Trade-Offs for the Longest Common Substring Problem
• Linear-Time Algorithm for Long LCF with k Mismatches
• Exact and Approximate Pattern Matching in the Streaming Model
• Probability Inequalities for Sums of Bounded Random Variables
• More Applications of the Polynomial Method to Algorithm Design
• Longest Common Substring with Approximately k Mismatches
• Deterministic methods to find primes
• Parameterized Algorithms
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• On the complexity of \(k\)-SAT

This page was built for publication: Longest common substring with approximately \(k\) mismatches