Weak repetitions in Sturmian strings

✍ Scribed by Ayşe Karaman

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 117 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00574-1

✦ Synopsis

In this paper, we analyze the weak repetitions in Sturmian strings and show that an optimally e cient algorithm to compute the weak repetitions in Sturmian strings according to the output encodings deÿned in the literature is quadratic in the string length. Finally, we present an encoding that leads to a linear-time algorithm.