File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: An efficient online algorithm for square detection

TitleAn efficient online algorithm for square detection
Authors
Leung, HFPeng, ZTing, HF
Issue Date2004
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3106, p. 432-439 How to Cite?
AbstractA square is a string of characters that can be divided into two identical substrings. The problem of detecting squares in a string finds applications in many areas such as bioinformatics and data compression. In this paper, we give the first efficient online algorithm for the problem. Given any input string, our algorithm reports the first square in the string using O(n log2 n) time where n is the position in the string where the square ends. This time complexity is only a factor of O(log n) larger than that of an optimal offline algorithm. © Springer-Verlag Berlin Heidelberg 2004.
Persistent Identifierhttp://hdl.handle.net/10722/93467
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLeung, HFen_HK
dc.contributor.authorPeng, Zen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T15:02:02Z-
dc.date.available2010-09-25T15:02:02Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3106, p. 432-439en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93467-
dc.description.abstractA square is a string of characters that can be divided into two identical substrings. The problem of detecting squares in a string finds applications in many areas such as bioinformatics and data compression. In this paper, we give the first efficient online algorithm for the problem. Given any input string, our algorithm reports the first square in the string using O(n log2 n) time where n is the position in the string where the square ends. This time complexity is only a factor of O(log n) larger than that of an optimal offline algorithm. © Springer-Verlag Berlin Heidelberg 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleAn efficient online algorithm for square detectionen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35048876784en_HK
dc.identifier.hkuros109463en_HK
dc.identifier.hkuros92460-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048876784&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3106en_HK
dc.identifier.spage432en_HK
dc.identifier.epage439en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridLeung, HF=7202811431en_HK
dc.identifier.scopusauthoridPeng, Z=8853602300en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats