A sublinear time string prefix square detection algorithm

Autor:	Jung-Hua Hsu, Yung-Tsang Chang, S. S. Yu
Rok vydání:	2006
Předmět:	Average-case complexity Discrete mathematics Algebra and Number Theory Correctness Sublinear function Applied Mathematics String (computer science) Commentz-Walter algorithm Rabin–Karp algorithm law.invention law Boyer–Moore string search algorithm Algorithm Time complexity Analysis Mathematics
Zdroj:	Journal of Discrete Mathematical Sciences and Cryptography. 9:87-95
ISSN:	2169-0065 0972-0529
DOI:	10.1080/09720529.2006.10698063
Popis:	In this paper, an algorithm is proposed to detect the occurrence of a prefix square concurrently when a string is inputted. Some properties of certain variables are studied in order to show the correctness and the time complexity of this algorithm. The time complexity of this algorithm is proved to be not only linear but also sublinear.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6f0b8e7e5463cc552560ce496f9b6b97 https://doi.org/10.1080/09720529.2006.10698063 Zobrazit plný text záznamu