TY - GEN

T1 - Online and dynamic recognition of squarefree strings

AU - Jansson, Jesper Andreas

AU - Peng, Zeshan

PY - 2005/10/24

Y1 - 2005/10/24

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26844524061&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

T3 - Lecture Notes in Computer Science

SP - 520

EP - 531

BT - Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29-September 2, 2005. Proceedings

A2 - Jedrzejowicz, Joanna

A2 - Szepietowski, Andrzej

T2 - 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005

Y2 - 29 August 2005 through 2 September 2005

ER -