Поиск периодичности в строках

Косов Григорий Сергеевич

Аннотация


В работе описывается алгоритм, позволяющий находить все максимальные повторения в заданной строке с временной сложностью О(n log(n)) и пространственной сложностью О(n). Также в работе приведено доказательство теоремы о циклическом сдвиге и частичное доказательство теоремы, улучшающей временную сложность алгоритм.