# Longest common substrings with k mismatches

Research output: Contribution to journal › Article › Scientific › peer-review

### Standard

**Longest common substrings with k mismatches.** / Flouri, Tomas; Giaquinta, Emanuele; Kobert, Kassian; Ukkonen, Esko.

Research output: Contribution to journal › Article › Scientific › peer-review

### Harvard

*Information Processing Letters*, vol. 115, no. 6-8, pp. 643-647. https://doi.org/10.1016/j.ipl.2015.03.006

### APA

*Information Processing Letters*,

*115*(6-8), 643-647. https://doi.org/10.1016/j.ipl.2015.03.006

### Vancouver

### Author

### Bibtex - Download

}

### RIS - Download

TY - JOUR

T1 - Longest common substrings with k mismatches

AU - Flouri, Tomas

AU - Giaquinta, Emanuele

AU - Kobert, Kassian

AU - Ukkonen, Esko

N1 - VK: Tarhio, J.

PY - 2015

Y1 - 2015

N2 - 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(nlogm)O(nlogm) 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.

AB - 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(nlogm)O(nlogm) 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.

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

KW - Combinatorial problems

KW - Hamming distance

KW - Longest common substring

KW - String algorithms

UR - http://dx.doi.org/10.1016/j.ipl.2015.03.006

U2 - 10.1016/j.ipl.2015.03.006

DO - 10.1016/j.ipl.2015.03.006

M3 - Article

VL - 115

SP - 643

EP - 647

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 6-8

ER -

ID: 2010307