Considere as seguintes definições extraídas de O número de execuções em uma sequência de caracteres por W. Rytter. Observe que palavra, string e substring são praticamente sinônimos.

Uma execução em uma sequência é um segmento periódico não extensível (com o mesmo período mínimo) em uma sequência.

Um período p de uma palavra w é qualquer número inteiro positivo p tal que w [i] = w [i + p] sempre que ambos os lados desta equação são definidos. Let per (w) indica o tamanho do menor período de w. Dizemos que uma palavra w é periódica se s por (w) <= | w | / 2.

Por exemplo, considere a sequência x = abcab. per(abcab) = 3como x[1] = x[1+3] = a, x[2]=x[2+3] = be não há período menor. A sequência abcabnão é, portanto, periódica. No entanto, a sequência ababé periódica conforme (abab) = 2.

Uma execução (ou periodicidade máxima) em uma string w é um intervalo [i ... j] com j> = i, de modo que

• w [i ... j] é uma palavra periódica com o período p = por (w [i ... j])
• É o máximo. Formalmente, nem w [i-1] = w [i-1 + p] nem w [j + 1] = w [j + 1-p]. Informalmente, a execução não pode estar contida em uma execução maior com o mesmo período.

Denote por RUNS (w) o conjunto de execuções de w.

Exemplos

As quatro execuções de atattattsão [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

A sequência aabaabaaaacaacaccontém as 7 execuções a seguir:

[1,2] = aa, [4,5] = aa, [7,10] = aaaa, [12,13] = aa, [13,16] = acac, [1,8] = aabaabaa, [9 , 15] = aacaaca.

Sua saída deve ser uma lista de execuções. Cada execução deve especificar o intervalo que representa, mas não precisa gerar a própria substring. A formatação exata pode ser o que for mais conveniente para você.

Os exemplos usam a indexação 1, mas você pode usar a indexação 0, se for mais conveniente.

TAREFA

Escreva o código que forneceu uma sequência w, execute RUNS (w).

Idiomas e entrada

Você pode usar qualquer idioma que desejar e pegar a string de entrada da forma que for mais conveniente. No entanto, você deve fornecer um programa completo e mostrar um exemplo do seu código em execução na entrada de exemplo.

Pitão, 38 bytes

{smm,hk+ekdfgaFTdcx1xM.ttB+0qVQ>QdZ2Sl

  m                                 SlQ   map for d in [1, …, len(input)]:
                            qVQ>Qd          pairwise equality of input[:-d] and input[d:]
                        tB+0                duplicate this list, prepending 0 to one copy
                      .t          Z         transpose, padding with 0
                    xM                      pairwise xor
                  x1                        find all occurrences of 1
                 c                 2        chop into groups of 2
           f                                filter for groups T such that:
             aFT                              the absolute difference between its elements
            g   d                             is greater than or equal to d
   m                                        map for groups k:
     hk                                       first element
    ,  +ekd                                   pair with the last element plus d
 s                                        concatenate
}                                         deduplicate

Suíte de teste

CJam, 66

q:A,2m*{~A>_@)_@<2*@@2*<=},{_2$-2>2,.+={+}&}*]{[_1=\)\0=2*)+]}%_&p

Experimente online

Breve explicação:

O algoritmo funciona em 4 etapas (as 3 primeiras correspondendo aos 3 blocos principais que você pode observar):

1. Encontre todos os pares de [índices de comprimento] que correspondem a uma substring duplicada (como um aba aba aaacaacac); estas são partes de execuções.
2. Concatene os pares que fazem parte da mesma execução, ou seja, índices consecutivos e a mesma duração / período.
3. Construa as execuções reais, obtendo o índice mínimo e o índice máximo + 2 * comprimento - 1.
4. No final, remova as execuções duplicadas (que são o mesmo intervalo obtido com um período diferente)

Eu gostaria de jogar mais, então tudo isso está sujeito a alterações.