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 language | English (US) |
---|---|
Pages (from-to) | 17-20 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 39 |
Issue number | 1 |
DOIs | |
State | Published - 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