Поиск неизвестной повторяющейся подстроки

#java #алгоритм

Есть длинная периодическая дробь по произвольному основанию, как найти её период?
Т.е. найти повторяющуюся подстроку. 
    

Ответы

Ответ 1

Надо считать цифры с шагом 1 и шагом 2 одновременно. Когда остатки от деления совпадут,
это будет означать, что ты находишься внутри периода. С этого мета просчитываешь ещё
один цикл до получения того же остатка - так определяется длина периода.

Если нужно ещё минимальное начала периодической части, то считаешь заново две последовательности,
одна из которых впереди на длину периода. Когда остатки совпадут, начало будет найдено.

В первой части можно вместо одновременного вычисления один раз промотать вперёд на
длину заведомо большую длины предпериода (т. е. значение знаменателя).