https://scholars.lib.ntu.edu.tw/handle/123456789/118064
標題: | Efficient on-line repetition detection | 作者: | Hong, Jin-Ju Chen, Gen-Huey |
關鍵字: | On-line detection; Repetition; Square | 公開日期: | 2008 | 起(迄)頁: | 554-563 | 來源出版物: | Theoretical Computer Science | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-53249147123&doi=10.1016%2fj.tcs.2008.08.038&partnerID=40&md5=40c75ea8a25d454bd353e83876280d83 | DOI: | 10.1016/j.tcs.2008.08.038 | SDG/關鍵字: | On-line detection; Repetition; Square |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。