Space efficient search for maximal repetitions
type: Item
instance of: scholarly article
title: Space efficient search for maximal repetitions
zbMATH Open document ID: 1076.68054
author: Leszek Gąsieniec
author: Igor Potapov
author: Roman Kolpakov
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
review text: For the task to find maximal repetitions in a word of length \(n\) there exist exhaustive algorithms. It is, however, interesting with which time and space limitations this can be achieved. The effort of previously known algorithms is decreased, introducing only minor restrictions.
reviewed by: Gunther Schmidt
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 2184109
zbMATH Keywords: space efficiency
zbMATH Keywords: repetitions
zbMATH Keywords: algorithms on words
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.01.006
OpenAlex ID: W1984098563
cites work: Q4849531
cites work: Squares, cubes, and time-space efficient string searching
cites work: Time-space-optimal string matching
cites work: The zooming method: A recursive approach to time-space efficient string-matching
cites work: Algorithms on Strings, Trees and Sequences
cites work: Q4934345
cites work: Q3659988
cites work: An O(n log n) algorithm for finding all repetitions in a string
DOI: 10.1016/J.TCS.2005.01.006
Recommended article: Q4453462
Recommended article: Q4737696
Recommended article: Faster Algorithms for Computing Maximal Multirepeats in Multiple Sequences
Recommended article: Q5747388
Recommended article: Almost linear time computation of maximal repetitions in run length encoded strings
Recommended article: Optimal Parallel Searching an Array for Certain Repetitions
Recommended article: Q4454546
Recommended article: Fast algorithms for finding a minimum repetition representation of strings and trees
Recommended article: Space-time trade-offs for finding shortest unique substrings and maximal unique matches
description: scientific article; zbMATH DE number 2184109