In this paper, given an input string
S and thresholds
L and
D, we would like to extract all (
D,
L)-supermaximal approximate repeats (
β,
β′) of
S. One useful application of extracting all (
D,
L)-supermaximal approximate repeats (
β,
β′) is to find all longest possible substrings
β of
S such that there exist some other substring
β′ of
S where
β and
β′ have edit-distance at most
D and their respective lengths are at least
L. This algorithm can be easily applied to the case where there are multiple input strings
S
1,
S
2,...,
S
n
if we first concatenate the input strings into one long subject string
S with a special symbol
$``\sharp"$``\sharp" for separation:
S1\sharp S2\sharp¼\sharp SnS_1\sharp S_2\sharp\ldots\sharp S_n. The running time complexity of our algorithm is
O(
DN
2) where
N=|
S
1|+|
S
2|+⋯+|
S
n
|.