Detection of periodicities and string-matching in real time

A. O. Slisenko

Zapiski Nauchnykh Seminarov POMI, Theoretical application of methods of mathematical logic. Part III, Tome 105 (1981), pp. 62-173

Résumé

The paper contains a detailed description of an algorithm which finds in real time all the periodicities in input string. As a computer model the author uses random access machine with registers of asymptotically minimal length, i.e. $\log n+\operatorname{const}$, where $n$ is the length of input string. In fact, the algorithm gives real-time procedures for some other known string-identification problems: string-matching, finding the longest common substring, finding longest repetitions and so on.