https://scholars.lib.ntu.edu.tw/handle/123456789/105051
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor | 國立臺灣大學資訊工程學系 | zh_TW |
dc.contributor.author | Chen, Gen-Huey | en |
dc.contributor.author | Hong, Jin-Ju | en |
dc.contributor.author | Lu, Hsueh-I | en |
dc.creator | Chen, Gen-Huey; Hong, Jin-Ju; Lu, Hsueh-I | - |
dc.date | 2005 | - |
dc.date.accessioned | 2006-09-27T10:51:55Z | - |
dc.date.accessioned | 2018-06-29T12:46:12Z | - |
dc.date.available | 2006-09-27T10:51:55Z | - |
dc.date.available | 2018-06-29T12:46:12Z | - |
dc.date.issued | 2005 | - |
dc.identifier | 20060927122849695480 | zh_TW |
dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/20060927122849695480 | - |
dc.description.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. | en |
dc.format | application/pdf | zh_TW |
dc.format.extent | 169323 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language | zh-TW | zh_TW |
dc.language.iso | zh_TW | - |
dc.publisher | 臺北市:國立臺灣大學資訊工程學系 | zh_TW |
dc.source | http://www.csie.ntu.edu.tw/~hil/paper/cpm05.pdf | zh_TW |
dc.subject | algorithm | - |
dc.subject | square Detection | - |
dc.title | An Optimal Algorithm for Online Square Detection | en |
dc.type | other | en |
dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/20060927122849695480/1/cpm05.pdf | - |
item.languageiso639-1 | zh_TW | - |
item.cerifentitytype | Products | - |
item.fulltext | with fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_1843 | - |
item.openairetype | other | - |
item.grantfulltext | open | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.orcid | 0000-0002-6968-6747 | - |
crisitem.author.orcid | 0000-0002-5755-2338 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。