An optimal algorithm to compute all the covers of a string (Q1329417): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / 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
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