https://scholars.lib.ntu.edu.tw/handle/123456789/105051
Title: | An Optimal Algorithm for Online Square Detection | Authors: | Chen, Gen-Huey Hong, Jin-Ju Lu, Hsueh-I |
Keywords: | algorithm;square Detection | Issue Date: | 2005 | Publisher: | 臺北市:國立臺灣大學資訊工程學系 | Abstract: | A square is the concatenation of two identical non-empty strings. Let S be the input string which is given character by character. Let m be the (unknown) smallest integer such that the m-th prefix of S contains a square. The online square detection problem is to determine m as soon as the m-th character of S is read. The best previously known algorithm of the online square detection problem, due to Leung, Peng, & Ting, runs in O(mlog2m) time. We improve the time complexity to O(mlog β), where β is the number of distinct characters in the m-th prefix of the input string. It is not difficult to implement our algorithm to run in expected O(m) time. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/20060927122849695480 | Other Identifiers: | 20060927122849695480 |
Appears in Collections: | 資訊管理學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.