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.
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 ...
Williams, Robert (2006)Latent Semantic Analysis, when used for automated essay grading, makes use of document word count vectors for scoring the essays against domain knowledge. Words in the domain knowledge documents and essays are counted, ...
Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...