1 Search Results for "Ilie, Lucian"

Document
DOI: 10.4230/LIPIcs.STACS.2008.1344
Understanding Maximal Repetitions in Strings

Authors: Maxime Crochemore and Lucian Ilie

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The cornerstone of any algorithm computing all repetitions in a string of length $n$ in ${mathcal O(n)$ time is the fact that the number of runs (or maximal repetitions) is ${mathcal O(n)$. We give a simple proof of this result. As a consequence of our approach, the stronger result concerning the linearity of the sum of exponents of all runs follows easily.
Cite as

Maxime Crochemore and Lucian Ilie. Understanding Maximal Repetitions in Strings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 11-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{crochemore_et_al:LIPIcs.STACS.2008.1344,
  author =	{Crochemore, Maxime and Ilie, Lucian},
  title =	{{Understanding Maximal Repetitions in Strings}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{11--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1344},
  URN =		{urn:nbn:de:0030-drops-13442},
  doi =		{10.4230/LIPIcs.STACS.2008.1344},
  annote =	{Keywords: Combinatorics on words, repetitions in strings, runs, maximal repetitions, maximal periodicities, sum of exponents}
}
  • Refine by Author
  • 1 Crochemore, Maxime
  • 1 Ilie, Lucian

  • Refine by Classification

  • Refine by Keyword
  • 1 Combinatorics on words
  • 1 maximal periodicities
  • 1 maximal repetitions
  • 1 repetitions in strings
  • 1 runs
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact