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 ).
Here is a linear solution to this problem:
Let's compute prefix function for the given string(like in Knuth-Morris-Pratt's algorithm).
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.