Longest common substrings with k mismatches

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

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

Organisaatiot

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut643-647
JulkaisuInformation Processing Letters
Vuosikerta115
Numero6-8
TilaJulkaistu - 2015
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

    Tutkimusalat

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

Lataa tilasto

Ei tietoja saatavilla

ID: 2010307