https://scholars.lib.ntu.edu.tw/handle/123456789/105051
標題: | An Optimal Algorithm for Online Square Detection | 作者: | Chen, Gen-Huey Hong, Jin-Ju Lu, Hsueh-I |
關鍵字: | algorithm;square Detection | 公開日期: | 2005 | 出版社: | 臺北市:國立臺灣大學資訊工程學系 | 摘要: | 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 | 其他識別: | 20060927122849695480 |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。