Efficient on-line repetition detection
Resource
Theoretical Computer Science 407 (1-3): 554-563
Journal
Theoretical Computer Science
Pages
554-563
Date Issued
2008
Date
2008
Author(s)
Hong, Jin-Ju
Abstract
A repetition is a nonempty string of the form Xq, where q ≥ 2. Given a string S character by character and the value of q, the on-line repetition detection problem is to detect and report the first repetition in S, if it exists, in an on-line manner. Leung, Peng and Ting first studied the problem for q = 2 and gave an O (m log2 m) time algorithm (refer to [H.-F. Leung, Z. Peng, H.-F. Ting, An efficient algorithm for online square detection, Theoretical Computer Science 363 (1) (2006) 69-75]), where m is the ending position of the first repetition in S. In this paper, we improve the above cited work by reducing the time complexity to O (m log β), where β is the number of distinct characters in the first m characters of S. Moreover, we also solve the problem for q ≥ 3 with the same time complexity. © 2008 Elsevier B.V. All rights reserved.
Subjects
On-line detection; Repetition; Square
Other Subjects
On-line detection; Repetition; Square
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
48.pdf
Size
1012.84 KB
Format
Adobe PDF
Checksum
(MD5):9ae0c343eb922437f4fed92120fe0df5