Locating All Maximal Approximate Runs in a String

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

Contributor : Maxime Crochemore <>
Submitted on : Friday, June 1, 2018 - 6:08:19 PM
Last modification on : Tuesday, July 3, 2018 - 8:43:49 AM
Long-term archiving on: Sunday, September 2, 2018 - 1:13:23 PM


  • HAL Id : hal-01798044, version 1



Mika Amit, Maxime Crochemore, Gad Landau. Locating All Maximal Approximate Runs in a String. Combinatorial Pattern Matching, 2013, Bad Herrenalb, Germany. ⟨hal-01798044⟩



Record views


Files downloads