Abstract
We study here a problem of finding all maximal repetitions in a string of length n. We show that the problem can be solved in time O(nlogn) in the presence of constant extra space and general (unbounded) alphabets. Subsequently we show that in the model with a constant size alphabet the problem can be solved in time O(n) with a help of o(n) extra space. Previously best known algorithms require linear additional space in both models.
Original language | English (US) |
---|---|
Pages (from-to) | 35-48 |
Number of pages | 14 |
Journal | Theoretical Computer Science |
Volume | 339 |
Issue number | 1 |
DOIs | |
State | Published - Jun 11 2005 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science