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
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?
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
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
References

 

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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats