A note on the longest common substring with k-mismatches problem

DOI10.1016/J.IPL.2015.03.003zbMATH Open1328.68329arXiv1409.7217OpenAlexW2024243150MaRDI QIDQ2345875FDOQ2345875

Authors: Szymon Grabowski 

Publication date: 21 May 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: The recently introduced longest common substring with $k$-mismatches ($k$-LCF) problem is to find, given two sequences $S_1$ and $S_2$ of length $n$ each, a longest substring $A_1$ of $S_1$ and $A_2$ of $S_2$ such that the Hamming distance between $A_1$ and $A_2$ is at most $k$. So far, the only subquadratic time result for this problem was known for $k=1$~cite{FGKU2014}. We first present two output-dependent algorithms solving the $k$-LCF problem and show that for $k=O(lo{g}^{1-varepsilon}n)$, where $varepsilon>0$, at least one of them works in subquadratic time, using $O(n)$ words of space. The choice of one of these two algorithms to be applied for a given input can be done after linear time and space preprocessing. Finally we present a tabulation-based algorithm working, in its range of applicability, in $O(n^{2}logmin(k+el{l}_0,sigma)/logn)$ time, where $el{l}_0$ is the length of the standard longest common substring.

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

Recommendations

• Longest common substrings with \(k\) mismatches
• Linear-time algorithm for long LCF with \(k\) mismatches
• Longest common substring with approximately \(k\) mismatches
• Longest common substring with approximately \(k\) mismatches
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings

zbMATH Keywords

combinatorial problemsstring algorithmsword-level parallelismlongest common substring with \(k\)-mismatches

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Dictionary matching and indexing with errors and don't cares
• Title not available (Why is that?)
• Approximate pattern matching with \(k\)-mismatches in packed text
• Computing the longest common substring with one mismatch
• Longest common substrings with \(k\) mismatches

Cited In (9)

• Longest common prefixes with \(k\)-errors and applications
• Longest common prefix with mismatches
• Linear-time algorithm for long LCF with \(k\) mismatches
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Longest common factor after one edit operation
• Longest common substring with approximately \(k\) mismatches
• Computing the longest common substring with one mismatch
• Longest common substrings with \(k\) mismatches
• Longest common substring with approximately \(k\) mismatches

This page was built for publication: A note on the longest common substring with \(k\)-mismatches problem

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