An optimal algorithm to compute all the covers of a string (Q1329417)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An optimal algorithm to compute all the covers of a string |
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
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
