File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An efficient algorithm for online square detection

TitleAn efficient algorithm for online square detection
Authors
Leung, HFPeng, ZSTing, HF
KeywordsOnline algorithms
Square-free detection
Squares
String processing
Issue Date2006
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2006, v. 363 n. 1, p. 69-75 How to Cite?
DOI: http://dx.doi.org/10.1016/j.tcs.2006.06.011
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 log2 h) time where h is the length of the longest prefix of the input string that does not contain a square. © 2006 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89143
ISSN
0304-3975
2021 Impact Factor: 1.002
2020 SCImago Journal Rankings: 0.464
ISI Accession Number ID
WOS:000241545600008
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLeung, HFen_HK
dc.contributor.authorPeng, ZSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-06T09:52:55Z-
dc.date.available2010-09-06T09:52:55Z-
dc.date.issued2006en_HK
dc.identifier.citationTheoretical Computer Science, 2006, v. 363 n. 1, p. 69-75en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89143-
dc.description.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 log2 h) time where h is the length of the longest prefix of the input string that does not contain a square. © 2006 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectOnline algorithmsen_HK
dc.subjectSquare-free detectionen_HK
dc.subjectSquaresen_HK
dc.subjectString processingen_HK
dc.titleAn efficient algorithm for online square detectionen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=363:1&spage=69&epage=75&date=2006&atitle=An+efficient+algorithm+for+online+square+detectionen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.tcs.2006.06.011en_HK
dc.identifier.scopuseid_2-s2.0-33749238905en_HK
dc.identifier.hkuros134746en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33749238905&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume363en_HK
dc.identifier.issue1en_HK
dc.identifier.spage69en_HK
dc.identifier.epage75en_HK
dc.identifier.isiWOS:000241545600008-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLeung, HF=7202811431en_HK
dc.identifier.scopusauthoridPeng, ZS=8853602300en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats