The Prague Stringology Club Workshop 2000
Frantisek Franek, Weilin Lu and William F. Smyth
Repetitions in two-pattern strings
| Abstract: |
| A recent paper shows that it can be determined in O(n) time whether or not a given string x of length n is a substring of an infinite Sturmian string; further, if x is such a substring, that the repetitions in x can be computed in Theta(n) time, generalizing a similar result for Fibonacci strings. In her M.Sc. thesis W. Lu extended these results to "two-pattern" strings formed recursively from concatenations of strings piq and pjq, where p and q are so-called "suitable patterns". Sturmian strings thus constitute the special case when p=a, q=b, |j-i|=1, while Fibonacci strings constitute the special case of Sturmian strings when i=1. In this paper we significantly relax the conditions for "suitable patterns" while showing that the repetitions can still be determined in Theta(n) time, thus significantly extending the class of strings whose repetitions can be calculated in linear time. This result is a part of an ongoing two-pronged research effort to identify and describe the class of strings whose repetitions can be determined in linear time and to show (or refute) that, in general, repetitions in any string can be listed in a list of a linear length using a succinct notation of "runs" even though the list itself cannot be calculated in a linear time. |
| Download paper: |  |
 |
| PostScript |