Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102332
Title: Online detection of repetitions with backtracking
Authors: Kosolobov, D.
Issue Date: 2015
Publisher: Springer Verlag
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.
Keywords: BACKTRACKING
ONLINE ALGORITHM
REPETITION-FREE
SQUARE-FREE
PATTERN MATCHING
BACKTRACKING
FOLLOWING PROBLEM
ON-LINE ALGORITHMS
ON-LINE DETECTION
ON-LINE FASHION
REPETITION-FREE
SQUARE-FREE
WORKING TIME
ALGORITHMS
URI: http://hdl.handle.net/10995/102332
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84949009893
PURE ID: 559635
43f121da-563b-406d-9e34-4bc83d9d8a8c
ISSN: 3029743
ISBN: 9783319199283
DOI: 10.1007/978-3-319-19929-0_25
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84949009893.pdf231,79 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.