On-Line Repetition Detection

摘要

A q-repetition is the concatenation of q copies of a primitive string, where q ≥ 2. Given a string S character by character, the on-line repetition detection problem is to determine whether S contains a q-repetition in an on-line manner. For q = 2, the problem can be solved in O(m log β) time, where m is the ending position of the first 2-repetition and β is the number of distinct characters in the m-th prefix of 5. In this paper, we present an on-line algorithm that can detect a q-repetition for q ≥ 3 with the same time complexity.