Space efficient search for maximal repetitions (Q557913): Difference between revisions

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.

0 references

reviewed by

Gunther Schmidt

0 references

zbMATH Keywords

space efficiency

0 references

repetitions

0 references

algorithms on words

0 references

complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.tcs.2005.01.006

0 references

cites work

Q4849531

0 references

Squares, cubes, and time-space efficient string searching

0 references

Time-space-optimal string matching

0 references

The zooming method: A recursive approach to time-space efficient string-matching

0 references

Algorithms on Strings, Trees and Sequences

0 references

Q4934345

0 references

Q3659988

0 references

An O(n log n) algorithm for finding all repetitions in a string

0 references

Identifiers

zbMATH Open document ID

1076.68054

0 references

DOI

10.1016/j.tcs.2005.01.006

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:557913

@@ Property / author @@
-Roman M. Kolpakov
@@ Property / author: Roman M. Kolpakov / rank @@
-Normal rank
@@ Property / author @@
+Roman M. Kolpakov
@@ Property / author: Roman M. Kolpakov / rank @@
+Normal rank
@@ Property / 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.
+Normal rank
@@ Property / reviewed by @@
+Gunther Schmidt
@@ Property / reviewed by: Gunther Schmidt / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+R15
@@ Property / Mathematics Subject Classification ID: 68R15 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q19
@@ Property / Mathematics Subject Classification ID: 68Q19 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Y16
@@ Property / Mathematics Subject Classification ID: 11Y16 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+2184109
@@ Property / zbMATH DE Number: 2184109 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+space efficiency
@@ Property / zbMATH Keywords: space efficiency / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+repetitions
@@ Property / zbMATH Keywords: repetitions / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+algorithms on words
@@ Property / zbMATH Keywords: algorithms on words / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+complexity
@@ Property / zbMATH Keywords: complexity / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2005.01.006
+Normal rank
@@ Property / OpenAlex ID @@
+W1984098563
@@ Property / OpenAlex ID: W1984098563 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4849531
@@ Property / cites work: Q4849531 / rank @@
+Normal rank
@@ Property / cites work @@
+Squares, cubes, and time-space efficient string searching
+Normal rank
@@ Property / cites work @@
+Time-space-optimal string matching
@@ Property / cites work: Time-space-optimal string matching / rank @@
+Normal rank
@@ Property / cites work @@
+The zooming method: A recursive approach to time-space efficient string-matching
+Normal rank
@@ Property / cites work @@
+Algorithms on Strings, Trees and Sequences
@@ Property / cites work: Algorithms on Strings, Trees and Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Q4934345
@@ Property / cites work: Q4934345 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3659988
@@ Property / cites work: Q3659988 / rank @@
+Normal rank
@@ Property / cites work @@
+An O(n log n) algorithm for finding all repetitions in a string
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:557913