Hong, Jin-JuJin-JuHongChen, Gen-HueyGen-HueyChen2009-04-292018-07-052009-04-292018-07-052008https://www.scopus.com/inward/record.uri?eid=2-s2.0-53249147123&doi=10.1016%2fj.tcs.2008.08.038&partnerID=40&md5=40c75ea8a25d454bd353e83876280d83A 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.application/pdf1037146 bytesapplication/pdfen-USOn-line detection; Repetition; SquareOn-line detection; Repetition; Squarejournal article10.1016/j.tcs.2008.08.0382-s2.0-53249147123http://ntur.lib.ntu.edu.tw/bitstream/246246/154732/1/48.pdf