Longest common substrings with k mismatches

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Tomas Flouri
  • Emanuele Giaquinta
  • Kassian Kobert
  • Esko Ukkonen

Research units

Abstract

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.

Details

Original languageEnglish
Pages (from-to)643-647
JournalInformation Processing Letters
Volume115
Issue number6-8
Publication statusPublished - 2015
MoE publication typeA1 Journal article-refereed

    Research areas

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

Download statistics

No data available

ID: 2010307