Finding period of a sequence

Question

I want to solve this problem:

For a given sequence, a[0], a[1], a[2],..., a[n-1], please find "period" of the sequence.
The period is the minimum integer k (k >= 1) that satisfies a[i] = a[i+k] for all valid i, and also k is a divisor of n.

My current solution is calculating all divisor of n (this is k) and test for all k, but it takes O(n * d(n)). I think it is slow.
Is there any efficient algorithm?

Answer 1

Apply Z-algorithm ( here and here) to given sequence.

Then find the first position i such that

  i+z[i] = n

and

  n mod i = 0

If such value of i exists, it is the shortest period