Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Faster Recovery of Approximate Periods over Edit Distance
verfasst von : Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
Erschienen in: String Processing and Information Retrieval
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The approximate period recovery problem asks to compute all approximate word-periods of a given word S of length n: all primitive words P (\(|P|=p\)) which have a periodic extension at edit distance smaller than \(\tau _p\) from S, where \(\tau _p = \lfloor \frac{n}{(3.75+\epsilon )\cdot p} \rfloor \) for some \(\epsilon >0\). Here, the set of periodic extensions of P consists of all finite prefixes of \(P^\infty \).
We improve the time complexity of the fastest known algorithm for this problem of Amir et al. [Theor. Comput. Sci., 2018] from \({\mathcal {O}}(n^{4/3})\) to \({\mathcal {O}}(n \log n)\). Our tool is a fast algorithm for Approximate Pattern Matching in Periodic Text. We consider only verification for the period recovery problem when the candidate approximate word-period P is explicitly given up to cyclic rotation; the algorithm of Amir et al. reduces the general problem in \({\mathcal {O}}(n)\) time to a logarithmic number of such more specific instances.