Please use this identifier to cite or link to this item:
|Title:||Online detection of repetitions with backtracking|
|Citation:||Kosolobov D. Online detection of repetitions with backtracking / D. Kosolobov. — DOI 10.1007/978-3-319-19929-0_25 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9133. — P. 295-306.|
|Abstract:||In this paper we present two algorithms for the following problem: given a string and a rational e > 1, detect in the online fashion the earliest occurrence of a repetition of exponent ≥ e in the string. 1. The first algorithm supports the backtrack operation removing the last letter of the input string. This solution runs in O(n log m) time and O(m) space, where m is the maximal length of a string generated during the execution of a given sequence of n read and backtrack operations. 2. The second algorithm works in O(n log σ) time and O(n) space, where n is the length of the input string and σ is the number of distinct letters. This algorithm is relatively simple and requires much less memory than the previously known solution with the same working time and space. © Springer International Publishing Switzerland 2015.|
|Appears in Collections:||Научные публикации, проиндексированные в SCOPUS и WoS CC|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.