Longest common substrings with k mismatches

Abstract: The longest common substring with

k

-mismatches problem is to find, given two strings

S_{1}

and

S_{2}

, a longest substring

A_{1}

of

S_{1}

and

A_{2}

of

S_{2}

such that the Hamming distance between

A_{1}

and

A_{2}

is

l e k

. We introduce a practical

O (n m)

time and

O (1)

space solution for this problem, where

n

and

m

are the lengths of

S_{1}

and

S_{2}

, respectively. This algorithm can also be used to compute the matching statistics with

k

-mismatches of

S_{1}

and

S_{2}

in

O (n m)

time and

O (m)

space. Moreover, we also present a theoretical solution for the

k = 1

case which runs in

O (n l o g m)

time, assuming

m l e n

, and uses

O (m)

space, improving over the existing

O (n m)

time and

O (m)

space bound of Babenko and Starikovskaya.

Cites Work

Cited In (12)

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