| Autor: |
Crestani, Fabio, Ferragina, Paolo, Sanderson, Mark, Hong, Jin-Ju, Chen, Gen-Huey |
| Zdroj: |
String Processing & Information Retrieval (9783540457749); 2006, p74-85, 12p |
| Abstrakt: |
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(mlogβ) 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 S. In this paper, we present an on-line algorithm that can detect a q-repetition for q≥3 with the same time complexity. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
