Space efficient search for maximal repetitions
- Leszek Ga̧sieniec(corresponding author),
- Roman Kolpakov,
- Igor Potapov
- University of Liverpool
Scholary Output:
Contribution to journal
Article
Peer-review
Open access
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.
Publication Information
Output type
Scholary Output:
Contribution to journal
Article
Peer-reviewOriginal language
English (US)Pages from-to (Number of pages)
Pages 35-48 (14 pages)Journal (Volume, Issue Number)
Theoretical Computer Science (Volume 339, Issue 1)Publication milestones
- Published - 06/11/2005
Publication status
Published - 06/11/2005
ISSN
0304-3975Publication IDs
- Scopus: 18544363750
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
SciVal
citations
5
SciVal
Author count
3
SciVal
Paper percentile
51
PlumX, opens in new tab
Citation count
4
Captures
6
Funding Details
This work is supported by the EPSRC Grant GR/R84917/01. ∗Corresponding author. E-mail addresses: [email protected] (L. Ga¸sieniec), [email protected] (R. Kolpakov), [email protected] (I. Potapov).