Cycle detection in bit-string [duplicate]

Question

Given a binary string of length N(<=10^5), I want to find the length of the cycle of the string. The length of the cycle will be at most 1000 and at least 1.

Example:

110110110110 length of cycle is 3(pattern repeating is 110)

000000 length of cycle is 1(pattern repeating is 0)

1101101101 length of cycle is 3(pattern repeating is 110)

I have tried to understand Floyd's cycle detection algorithm but I'm unable to understand how to apply in on this question.

How do I solve this problem efficiently? (I want an algorithm that runs in O(NlogN) or better ).

Answer 1

Here is a linear solution to this problem:

1. Let's compute prefix function for the given string(like in Knuth-Morris-Pratt's algorithm).

2. The answer is always n - p[n], where n is the length of the given string and p[i] is the value of the prefix function for the i-th position in the string. Proof:

   • The period is not smaller than n - p[n]. It is the case because for any period k, s[i] = s[i + k] for any i. Thus, n - p[n] is at least k due to the definition of the prefix function.

   • The period is not greater than k = n - p[n]. It is the case because s[i] = s[i + k] for all i due to the definition of the prefix function, which implies that k is a period.