Locating All Maximal Approximate Runs in a String
Résumé
An exact run in a string, T , is a non-empty substring of T that can be divided into adjacent non-overlapping identical substrings. Finding exact runs in strings is an important problem and therefore a well studied one in the strings community. For a given string T of length n, finding all maximal exact runs in the string can be done in O(n log n) time or O(n) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k, find every non-empty substring T of T such that changing at most k letters in T transforms it into a maximal exact run in T. We present an O(nk 2 log k log n k) algorithm.
Loading...