Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Friday, June 1, 2018 - 6:08:19 PM
Last modification on : Friday, September 16, 2022 - 1:48:58 PM
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