Trouver le motif répété le plus long dans une chaîne

Je cherche un algorithme efficace pour trouver le motif répété le plus long dans une chaîne.

Par exemple, considérez la chaîne de nombres suivante:

5431428571428571428571428571427623874534.

Comme vous pouvez le voir, 142857142857c'est le modèle le plus long qui est répété plusieurs fois (au moins deux fois) dans cette chaîne.

La chaîne répétée ne doit pas contenir d'idée plutôt que de force brute?

Le problème est étonnamment non trivial. Tout d'abord, deux algorithmes de force brute. Un carré ("motif répété") est donné par sa longueur $\ell$ et sa position $p$ , et prend du temps $O(\ell)$ pour vérifier. Si nous passons en revue tous les $\ell$ et $p$ , nous obtenons un algorithme $O(n^3)$ . Nous pouvons améliorer cela en bouclant d'abord sur $\ell$ , puis en balayant la chaîne avec deux pointeurs en cours à une distance de $\ell$ . De cette façon, on peut vérifier si un carré de longueur $2\ell$ existe en temps linéaire, ce qui donne un temps total de fonctionnement de $O(n^2)$ .

Kolpakov et Kucherov ont développé un algorithme pour trouver toutes les répétitions maximales dans un mot dans le temps $O(n)$ [1], et leur algorithme peut être utilisé pour trouver tous les carrés maximaux dans le temps $O(n)$ . Une répétition est un sous-mot de la forme $w^kx$ , où $k \geq 2$ et $x$ est un préfixe propre de $w$ . Le plus grand carré contenu dans cette répétition est $(w^{\lfloor k/2 \rfloor})^2$. En utilisant cette formule, étant donné toutes les répétitions maximales dans un mot (dont il n'y a que $O(n)$ plusieurs), on peut trouver le plus grand carré.

[1] Kolpakov, R. et Kucherov, G. (1999). Trouver des répétitions maximales dans un mot en temps linéaire . Dans Foundations of Computer Science, 1999. 40th Annual Symposium on (pp. 596-604). IEEE.