Online and dynamic recognition of squarefree strings

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

4 Citations (Scopus)

Abstract

The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets. Its running time is O(n log n), where n is the ending position of the first square, which matches the running times of the fastest known algorithms for the analogous offline problem. We also present a very simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string contains a square and if so, report it and stop.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29-September 2, 2005. Proceedings
EditorsJoanna Jedrzejowicz, Andrzej Szepietowski
Pages520-531
Number of pages12
Publication statusPublished - 24 Oct 2005
Externally publishedYes
Event30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland
Duration: 29 Aug 20052 Sep 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
VolumeLNCS 3618
ISSN (Print)0302-9743

Conference

Conference30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005
CountryPoland
CityGdansk
Period29/08/052/09/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this