Online and dynamic recognition of squarefree strings

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 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 in O(n log n) time, where n is the ending position of the first square. We also note that the same technique yields an O (n·(|Σn|+log n))-time algorithm for general alphabets, where |Σn| is the number of different symbols in the first n positions of the input string. (This is faster than the previously fastest method for general alphabets when |Σn| = o(log2 n).) Finally, we present a 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 is still squarefree.
Original languageEnglish
Pages (from-to)401-414
Number of pages14
JournalInternational Journal of Foundations of Computer Science
Volume18
Issue number2
DOIs
Publication statusPublished - 1 Apr 2007
Externally publishedYes

Keywords

  • Online algorithm
  • Square detection
  • Squarefree string

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Cite this