Space efficient search for maximal repetitions
- Leszek Ga̧sieniec(corresponding author),
- Roman Kolpakov,
- Igor Potapov
- University of Liverpool
Scholary Output:
Contribution to journal
Article
Research
Peer-reviewOpen access
Abstract
<p>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.</p>
Publication Information
Output type
Scholary Output:
Contribution to journal
Article
Research
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
SciVal
Author count
3
SciVal
citations
5
SciVal
Paper percentile
51
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Captures
6
Citation count
5
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).
