Encontre o padrão repetido mais longo em uma string

Estou procurando um algoritmo eficiente para encontrar o padrão repetido mais longo em uma string.

Por exemplo, considere a seguinte sequência de números:

5431428571428571428571428571427623874534.

Como você pode ver, 142857142857é o padrão mais longo repetido algumas vezes (pelo menos duas vezes) nessa sequência.

A sequência repetida não deve conter mais nenhuma ideia do que força bruta?

algorithms strings subsequences Juho
fonte

Você não definiu o que significa "algumas vezes", mas se "duas vezes" conta como "algumas vezes", então 142857não é o mais longo, porque 142857142857é mais longo. Eu acho que você deve editar a pergunta para esclarecer o que você quer dizer com "padrão repetido".

Tsuyoshi Ito

ponto muito bom. Vou atualizar a pergunta.

Você está exigindo que as ocorrências do padrão sejam separadas umas das outras? Porque, se não, 142857142857 ainda não é a repetição mais longa; 142857142857142857142 ocorre duas vezes. De qualquer forma, a resposta usual para perguntas como essa é "árvores de sufixo".

Respostas:

O problema é surpreendentemente não trivial. Primeiro, dois algoritmos de força bruta. Um quadrado ("padrão repetido") é dado por seu comprimento e posição , e leva tempo para verificar. Se passar por cima de tudo e , obtemos um algoritmo. Podemos melhorar isso primeiro dando um loop sobre e depois varrendo a string com dois ponteiros em execução a uma distância de $\ell$ $p$ $O(\ell)$ $\ell$ $p$ $O(n^3)$ $\ell$ $\ell$ . Dessa forma, é possível verificar seexisteum quadrado de comprimento $2\ell$ em tempo linear, em um tempo total de execução de $O(n^2)$ .

Kolpakov e Kucherov desenvolveram um algoritmo para encontrar todas as repetições máximas em uma palavra no tempo $O(n)$ [1], e seu algoritmo pode ser usado para encontrar todos os quadrados máximos no tempo $O(n)$ . Uma repetição é um subpalavra da forma $w^kx$ , onde $k \geq 2$ e $x$ é um prefixo adequado de $w$ . O maior quadrado contido nessa repetição é $(w^{\lfloor k/2 \rfloor})^2$ . Usando esta fórmula, dadas todas as repetições máximas em uma palavra (das quais existem apenas $O(n)$ muitas)), pode-se encontrar o quadrado maior.

[1] Kolpakov, R. & Kucherov, G. (1999). Encontrando repetições máximas em uma palavra em tempo linear . In Foundations of Computer Science, 1999. 40º Simpósio Anual sobre (pp. 596-604). IEEE.

Yuval Filmus
fonte