Longest common substrings with k mismatches

Tomas Flouri, Emanuele Giaquinta, Kassian Kobert, Esko Ukkonen

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)
364 Downloads (Pure)


The longest common substring with k -mismatches problem is to find, given two strings S1S1 and S2S2, a longest substring A1A1 of S1S1 and A2A2 of S2S2 such that the Hamming distance between A1A1 and A2A2 is ≤k . We introduce a practical O(nm)O(nm) time and O(1)O(1) space solution for this problem, where n and m are the lengths of S1S1 and S2S2, respectively. This algorithm can also be used to compute the matching statistics with k -mismatches of S1S1 and S2S2 in O(nm)O(nm) time and O(m)O(m) space. Moreover, we also present a theoretical solution for the k=1k=1 case which runs in O(nlog⁡m)O(nlog⁡m) time, assuming m≤nm≤n, and uses O(m)O(m) space, improving over the existing O(nm)O(nm) time and O(m)O(m) space bound of Babenko and Starikovskaya.
Original languageEnglish
Pages (from-to)643-647
JournalInformation Processing Letters
Issue number6-8
Publication statusPublished - 2015
MoE publication typeA1 Journal article-refereed


  • Combinatorial problems
  • Hamming distance
  • Longest common substring
  • String algorithms

Fingerprint Dive into the research topics of 'Longest common substrings with k mismatches'. Together they form a unique fingerprint.

  • Cite this

    Flouri, T., Giaquinta, E., Kobert, K., & Ukkonen, E. (2015). Longest common substrings with k mismatches. Information Processing Letters, 115(6-8), 643-647. https://doi.org/10.1016/j.ipl.2015.03.006