Обнаружение цикла в последовательности без повторения

Question

Я понимаю, что tortoise-hare как алгоритмы работают на итерированных последовательностях То есть для любого x, succ (x) = x0.

Я хотел бы реализовать algortihm, который может определять циклы как в детерминированных, так и в недетерминированных бесконечных повторяющихся последовательностях.

Последовательности могут иметь неповторяющуюся последовательность подстановок, например, в последовательности 1666666..., имеет префикс 1 и повторяющийся шаблон 6.

Этот алгоритм возвращает самый длинный повторяющийся шаблон в последовательности. Повторяющийся рисунок 001100110011... будет 0011, повторяющийся узор 22583575837583758... будет 58357.

Моя идея состояла в том, чтобы генерировать догадки о самой длинной длины шаблона, как-то оттуда, но я не могу привести в порядок.

Answer 1

Алгоритм tortoise-hare использует тот же адрес для идентификации циклов. Эта проблема требует другого типа алгоритма. Некоторая форма trie или структуры, такая как сжатие LZW, была бы там, где я бы искал решение.