Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    Extracting powers and periods in a word from its runs structure

    Access Status
    Fulltext not available
    Authors
    Crochemore, M.
    Iliopoulos, Costas
    Kubica, M.
    Kubica, M.
    Radoszewski, J.
    Rytter, W.
    Walen, T.
    Date
    2014
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Crochemore, M. and Iliopoulos, C. and Kubica, M. and Kubica, M. and Radoszewski, J. and Rytter, W. and Walen, T. 2014. Extracting powers and periods in a word from its runs structure. Theoretical Computer Science. 521: pp. 29-41.
    Source Title
    Theoretical Computer Science
    ISSN
    0304-3975
    School
    Department of Mathematics and Statistics
    URI
    http://hdl.handle.net/20.500.11937/48986
    Collection
    • Curtin Research Publications
    Abstract

    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.

    Related items

    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 ...
    • Does pain matter in the Australian Royal Commission into Aged Care Quality and Safety? A text mining study
      Atee, Mustafa ; Andreotta, Matthew; Lloyd, Rebecca; Whiting, Daniel; Alford, Marie; Morris, Thomas (2023)
      Background Pain is often poorly documented, assessed and managed in the Australian aged care sector. The Australian Government called for the Royal Commission into Aged Care Quality and Safety (RC) to investigate the ...
    • Effects of phonological neighbourhood density and frequency in picture naming
      Hameau, Solene; Biedermann, Britta ; Robidoux, Serje; Nickels, Lyndsey (2021)
      Speaking involves selecting a word among co-activated words in the lexicon. The factors determining which potentially co-activated words affect the production of spoken words remain underspecified. This research investigated ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.