Optimal superprimitivity testing for strings

Alberto Apostolico, Martin Farach, Costas S. Iliopoulos

    Research output: Contribution to journalArticlepeer-review

    Abstract

    A string w covers another string z if every position of z is within some occurrence of w in z. Clearly, every string is covered by itself. A string that is covered only by itself is superprimitive. We show that the property of being superprimitive is testable on a string of n symbols in O(n) time and space.

    Original languageEnglish (US)
    Pages (from-to)17-20
    Number of pages4
    JournalInformation Processing Letters
    Volume39
    Issue number1
    DOIs
    StatePublished - Jul 12 1991

    Keywords

    • Combinatorial problems
    • algorithms on words
    • analysis of algorithms
    • design of algorithms
    • period of a string
    • quasiperiod of a string
    • superprimitive strings

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications

    Cite this