کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436592 | 690017 | 2014 | 13 صفحه PDF | دانلود رایگان |
A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O(n)O(n) and that they can all be computed in O(n)O(n) time. We study some applications of this result. New simpler O(n)O(n) time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k , in particular squares for k=2k=2, and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25] and [26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem.
Journal: Theoretical Computer Science - Volume 521, 13 February 2014, Pages 29–41