Efficient on-line repetition detection

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(mlog2m) 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(mlogβ), 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.