Encuentra el patrón repetido más largo en una cadena

Estoy buscando un algoritmo eficiente para encontrar el patrón repetido más largo en una cadena.

Por ejemplo, considere la siguiente cadena de números:

5431428571428571428571428571427623874534.

Como puede ver, 142857142857es el patrón más largo que se repite un par de veces (al menos dos veces) en esta cadena.

La cadena repetida no debe contener ninguna idea en lugar de fuerza bruta.

El problema es sorprendentemente no trivial. Primero, dos algoritmos de fuerza bruta. Un cuadrado ("patrón repetido") viene dado por su longitud y posición , y toma tiempo para verificar. Si nos vamos sobre toda y , se obtiene un algoritmo. Podemos mejorar eso primero haciendo un bucle sobre y luego escaneando la cadena con dos punteros en ejecución a una distancia de . De esta manera, se puede verificar si existe un cuadrado de longitud en tiempo lineal, dando un tiempo total de ejecución de .$\ell$$p$$O(\ell)$$\ell$$p$$O(n^3)$$\ell$$\ell$$2\ell$$O(n^2)$

Kolpakov y Kucherov desarrollaron un algoritmo para encontrar todas las repeticiones máximas en una palabra en el tiempo [1], y su algoritmo se puede usar para encontrar todos los cuadrados máximos en el tiempo . Una repetición es una palabra parcial de la forma , donde y es un prefijo apropiado de . El cuadrado más grande contenido en esa repetición es . Usando esta fórmula, dadas todas las repeticiones máximas en una palabra (de las cuales solo hay muchas), se puede encontrar el cuadrado más grande.$O(n)$$O(n)$$w^kx$$k \geq 2$$x$$w$$(w^{\lfloor k/2 \rfloor})^2$$O(n)$

[1] Kolpakov, R. y Kucherov, G. (1999). Encontrar repeticiones máximas en una palabra en tiempo lineal . En Fundamentos de Ciencias de la Computación, 1999. 40º Simposio Anual sobre (pp. 596-604). IEEE