An optimal algorithm to compute all the covers of a string (Q1329417): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:57, 5 March 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
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
