Locating All Maximal Approximate Runs in a String - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Locating All Maximal Approximate Runs in a String

Maxime Crochemore

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.
Fichier principal
Vignette du fichier
paper_18.pdf (297.07 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-01798044 , version 1 (01-06-2018)

Identifiants

  • HAL Id : hal-01798044 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More