java – Finding an unknown repeated substring


There is a long periodic fraction in an arbitrary base, how to find its period? Those. find a duplicate substring.


It is necessary to count the numbers with step 1 and step 2 at the same time. When the remainders of the division match, it will mean that you are inside the period. From this meta, you calculate one more cycle until you get the same balance – this is how the length of the period is determined.

If you still need the minimum beginning of the periodic part, then you count again two sequences, one of which is ahead by the length of the period. When the remainders match, the beginning will be found.

In the first part, instead of simultaneously calculating, you can scroll forward once by a length that is obviously greater than the length of the preperiod (i.e., the value of the denominator).

Scroll to Top