An efficient algorithm for online square detection
Publication in refereed journal


Times Cited
Web of Science2WOS source URL (as at 17/10/2020) Click here for the latest count
Altmetrics Information
.

Other information
AbstractA square is a string that can be divided into two identical substrings. The problem of square detection has found applications in areas such as bioinformatics and data compression. There are many offline algorithms for the problem. In this paper, we give the first online algorithm for deciding whether a string contains a square. Our algorithm runs in total O(h log(2) h) time where h is the length of the longest prefix of the input string that does not contain a square. (C) 2006 Elsevier B.V. All rights reserved.
All Author(s) ListLeung HF, Peng ZS, Ting HF
Name of Conference10th International Computing and Combinatorics Conference (COCOON 2004)
Start Date of Conference17/08/2004
End Date of Conference20/08/2004
Place of ConferenceCheju Isl
Journal nameTheoretical Computer Science
Year2006
Month10
Day25
Volume Number363
Issue Number1
PublisherELSEVIER SCIENCE BV
Pages69 - 75
ISSN0304-3975
eISSN1879-2294
LanguagesEnglish-United Kingdom
Keywordsonline algorithms; square-free detection; squares; string processing
Web of Science Subject CategoriesComputer Science; Computer Science, Theory & Methods; COMPUTER SCIENCE, THEORY & METHODS

Last updated on 2020-18-10 at 01:07