Longest common substrings with \(k\) mismatches

DOI10.1016/j.ipl.2015.03.006zbMath1328.68326arXiv1409.1694OpenAlexW1996780636WikidataQ58054124 ScholiaQ58054124MaRDI QIDQ2345877

Kassian Kobert, Esko Ukkonen, Emanuele Giaquinta, Tomáš Flouri

Publication date: 21 May 2015

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

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

zbMATH Keywords

combinatorial problemsHamming distancestring algorithmslongest common substring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (11)

Efficient computation of sequence mappability ⋮ A new distributed alignment-free approach to compare whole proteomes ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Near-optimal quantum algorithms for string problems ⋮ Dynamic and internal longest common substring ⋮ Longest Common Factor After One Edit Operation ⋮ Longest common substring made fully dynamic ⋮ A note on the longest common substring with \(k\)-mismatches problem ⋮ Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms. ⋮ Linear-Time Algorithm for Long LCF with k Mismatches ⋮ \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Computing the longest common substring with one mismatch
• Sublinear approximate string matching and biological applications
• Longest repeats with a block of \(k\) don't cares
• Sublinear Space Algorithms for the Longest Common Substring Problem
• A Fast Merging Algorithm
• Algorithms on Strings, Trees and Sequences
• Time-Space Trade-Offs for the Longest Common Substring Problem

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