Trouver la période d'une séquence

Question

Je veux résoudre ce problème :

Pour une séquence donnée, a[0], a[1], a[2],..., a[n-1] veuillez trouver la "période" de la séquence.
La période est le nombre entier minimal k (k >= 1) qui satisfait à a[i] = a[i+k] pour tous les i valides, et aussi k est un diviseur de n.

Ma solution actuelle est de calculer tous les diviseurs de n (c'est k) et de tester pour tous les k, mais cela prend O(n * d(n)) . Je pense que c'est lent.
Existe-t-il un algorithme efficace ?

Answer 1

Appliquer l'algorithme Z ( aquí y aquí ) à une séquence donnée.

Ensuite, trouvez la première position i tal que

  i+z[i] = n

y

  n mod i = 0

Si cette valeur de i existe, c'est la période la plus courte