An optimal algorithm to compute all the covers of a string (Q1329417): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 12:29, 31 January 2024

scientific article
Language Label Description Also known as
English
An optimal algorithm to compute all the covers of a string
scientific article

    Statements

    An optimal algorithm to compute all the covers of a string (English)
    0 references
    0 references
    1994
    0 references
    A string \(u\) is a cover of a string \(x\) if every letter in \(x\) is inside a copy of \(u\). For example \(aba\) is a cover of \(ababaabaabaaba\). This paper characterizes all covers of \(x\) in terms of an easily computed normal form for \(x\). This leads to an algorithm that computes all covers of \(x\) in time \(\Theta (| x |)\).
    0 references
    covers
    0 references

    Identifiers