Extracting powers and periods in a word from its runs structure
MetadataShow full item record
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) and that they can all be computed in O(n) time. We study some applications of this result. New simpler 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=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,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.
Showing items related by title, author, creator and subject.
Automatic Evaluation Stimuli - The Most Frequently Used Words to Describe Physical Activity and the Pleasantness of Physical Activity.Rebar, Amanda; Schoeppe, S.; Alley, S.; Short, C.; Dimmock, J.; Jackson, B.; Conroy, D.; Rhodes, R.; Vandelanotte, C. (2016)Physical activity is partially regulated by non-conscious processes including automatic evaluations - the spontaneous affective reactions we have to physical activity that lead us to approach or avoid physical activity ...
Crochemore, M.; Iliopoulos, Costas; Kubica, M.; Kubica, M.; Radoszewski, J.; Rytter, W.; Walen, T. (2014)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) and that they can all be computed in O(n) time. We study some applications of this ...
Mayall, Peter (2008)Learning and interpreting English in a commercial context is one of the hidden difficulties that students face when English is their second language. The difficulties are exacerbated when they are studying on-line or are ...