Linear-time algorithm for long LCF with k mismatches

DOI10.4230/LIPICS.CPM.2018.23MaRDI QIDQ5140788zbMATH OpenOpenAlexFDO

Authors Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 16 December 2020

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

zbMATH Keywords

difference coverHamming distanceheavy-light decompositionlongest common factorlongest common substring

Mathematics Subject Classification ID

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

Abstract: In the Longest Common Factor with $k$ Mismatches (LCF${}_k$) problem, we are given two strings $X$ and $Y$ of total length $n$, and we are asked to find a pair of maximal-length factors, one of $X$ and the other of $Y$, such that their Hamming distance is at most $k$. Thankachan et al. show that this problem can be solved in $mathcalO(nlo{g}^{k}n)$ time and $mathcalO(n)$ space for constant $k$. We consider the LCF${}_k$($ell$) problem in which we assume that the sought factors have length at least $ell$, and the LCF${}_k$($ell$) problem for $ell=Omega(lo{g}^{2k+2}n)$, which we call the Long LCF${}_k$ problem. We use difference covers to reduce the Long LCF${}_k$ problem to a task involving $m=mathcalO(n/lo{g}^{k+1}n)$ synchronized factors. The latter can be solved in $mathcalO(mlo{g}^{k+1}m)$ time, which results in a linear-time algorithm for Long LCF${}_k$. In general, our solution to LCF${}_k$($ell$) for arbitrary $ell$ takes $mathcalO(n+nlo{g}^{k+1}n/sqrtell)$ time.

Recommendations

• A note on the longest common substring with k-mismatches problem
• Longest common substrings with k mismatches
• Longest common substring with approximately \(k\) mismatches
• Longest common substring with approximately \(k\) mismatches
• Longest common prefixes with k-mismatches and applications

Cites work

• A Fast Merging Algorithm
• A note on the longest common substring with k-mismatches problem
• Algorithms on Strings, Trees and Sequences
• Applications of Path Compression on Balanced Trees
• Computing the longest common substring with one mismatch
• Dictionary matching and indexing with errors and don't cares
• Fast lightweight suffix array construction and checking
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Longest common prefixes with k-mismatches and applications
• Longest common substring with approximately \(k\) mismatches
• Longest common substrings with k mismatches
• Longest repeats with a block of \(k\) don't cares
• More applications of the polynomial method to algorithm design
• On the complexity of k-SAT
• Sorting jordan sequences in linear time using level-linked search trees
• Sublinear space algorithms for the longest common substring problem
• Time-space trade-offs for the longest common substring problem
• Which problems have strongly exponential complexity?

Cited in

(15)

• Efficient computation of sequence mappability
• Longest property-preserved common factor: a new string-processing framework
• A note on the longest common substring with k-mismatches problem
• Longest common substrings with k mismatches
• Longest common substring with approximately \(k\) mismatches
• scientific article; zbMATH DE number 4007744 (Why is no real title available?)
• Longest common substring made fully dynamic
• A linear-time algorithm for the 1-mismatch problem
• Longest common substring with approximately \(k\) mismatches
• Faster algorithms for 1-mappability of a sequence
• Near-optimal quantum algorithms for string problems
• Dynamic longest common substring in polylogarithmic time
• Substring complexity in sublinear space
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Longest common substring with gaps and related problems

Describes a project that uses

Uses Software

• ALFRED

This page was built for publication: Linear-time algorithm for long LCF with \(k\) mismatches

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