Como encontro a maior sequência em uma string que é repetida pelo menos uma vez?

9

Tentando resolver o seguinte problema:

  

Dada uma string de comprimento arbitrário, encontre a substring mais longa que ocorre mais de uma vez na string, sem sobreposições.

Por exemplo, se a string de entrada fosse ABCABCAB , a saída correta seria ABC . Você não poderia dizer ABCAB , porque isso só ocorre duas vezes quando as duas substrings se sobrepõem, o que não é permitido.

Existe alguma maneira de resolver isso razoavelmente rapidamente para cadeias contendo alguns milhares de caracteres?

(E antes que alguém pergunte, isso não é lição de casa. Estou procurando maneiras de otimizar a renderização de fractais Lindenmayer, porque eles tendem a gastar muito tempo para desenhar em níveis altos de iteração com um sistema de gráficos de tartaruga ingênuo. )

    
por Mason Wheeler 07.08.2012 в 22:30
fonte

4 respostas

3

Aqui está um exemplo para uma string de comprimento 11, que você pode generalizar

  • Defina o tamanho do pedaço como o chão (11/2) = 5

  • Digitalize a sequência em pedaços de 5 caracteres à esquerda para procurar por repetições. Haverá 3 comparações

    Left      Right
    Offset    Offset
     0         5
     0         6
     1         5
  • Se você encontrou uma duplicata, pronto. Caso contrário, reduza o comprimento do pedaço para 4 e repita até que o comprimento do pedaço vá para zero.

Aqui estão alguns pseudocódigo (obviamente não testados):

String s
int len = floor(s.length/2)
for int i=len; i>0; i--
    for j=0; j<=len-(2*i); j++
        for k=j+i; k<=len-i; k++
            if s.substr(j,j+i) == s.substr(k,k+i)
                return s.substr(j,j+i)
return null

Pode haver um erro "off-by-one", mas a abordagem deve ser sólida (e mínima).

    
por Jim Garrison 07.08.2012 / 22:53
fonte
2

parece um problema de árvore de sufixos. Crie a árvore de sufixos e, em seguida, localize o maior ramo compactado com mais de um filho (ocorre mais de uma vez na cadeia original). O número de letras nesse ramo comprimido deve ser o tamanho da maior subsequência.

encontrei algo semelhante aqui: link

Parece que isso pode ser feito em O (n).

    
por piotrek 07.08.2012 / 22:52
fonte
0

Primeiramente, precisamos definir o símbolo inicial de nossa substring e definir o comprimento. Iterar todas as posições de início possíveis e descobrir o comprimento fazendo a pesquisa binária pelo comprimento (se você puder encontrar o substr com o comprimento a, você pode encontrar com o comprimento maior, a função parece monótona, então a pesquisa bin deve estar bem). Então, encontrar substring igual é N, usando KMP ou Rabin-Karp, qualquer algoritmo linear é bom. Total N * N * log (N). Isso é muita complexidade? O código é algo como:

for(int i=0;i<input.length();++i)
    {
        int l = i;
        int r = input.length();
        while(l <= r)
        {
            int middle = l + ((r - l) >> 1);
            Check if string [i;middle] can be found in initial string. Should be done in O(n); You need to check parts of initial string [0,i-1], [middle+1;length()-1];
            if (found)
                l = middle + 1;
            else
                r = middle - 1;
        }
    }

Faz sentido?

    
por Roman Dzhabarov 07.08.2012 / 22:39
fonte
0

Este tipo de análise é feito frequentemente em seqüências genômicas. dê uma olhada neste papel. ele tem uma implementação eficiente (c ++) para resolver repetições: link pode ser o que você está procurando

    
por morishuz 21.05.2013 / 17:00
fonte