A sublinear time string prefix square detection algorithm
Yung-Tsang Chang, Jung-Hua Hsu, Shyr-Shen Yu · Journal of Discrete Mathematical Sciences and Cryptography · 2006
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.