Considere las siguientes definiciones tomadas de El número de ejecuciones en una cadena por W. Rytter. Tenga en cuenta que palabra, cadena y subcadena son todos sinónimos.

Una ejecución en una cadena es un segmento periódico no extensible (con el mismo período mínimo) en una cadena.

Un punto p de una palabra w es cualquier número entero positivo p tal que w [i] = w [i + p] siempre que se definan ambos lados de esta ecuación. Deje que por (w) denote el tamaño del período más pequeño de w. Decimos que una palabra w es periódica iff per (w) <= | w | / 2.

Por ejemplo, considere la cadena x = abcab. per(abcab) = 3como x[1] = x[1+3] = a, x[2]=x[2+3] = by no hay un período más pequeño. La cadena, abcabpor lo tanto, no es periódica. Sin embargo, la cadena ababes periódica según (abab) = 2.

Una ejecución (o periodicidad máxima) en una cadena w es un intervalo [i ... j] con j> = i, de modo que

• w [i ... j] es una palabra periódica con el período p = per (w [i ... j])
• Es maxima. Formalmente, ni w [i-1] = w [i-1 + p] ni w [j + 1] = w [j + 1-p]. Informalmente, la ejecución no puede estar contenida en una ejecución mayor con el mismo período.

Denote por RUNS (w) el conjunto de corridas de w.

Ejemplos

Las cuatro carreras de atattattson [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

La cadena aabaabaaaacaacaccontiene las siguientes 7 ejecuciones:

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

Su salida debe ser una lista de ejecuciones. Cada ejecución debe especificar el intervalo que representa pero no necesita generar la subcadena en sí. El formato exacto puede ser lo que sea conveniente para usted.

Los ejemplos usan la indexación 1, pero puede usar la indexación 0 si es más conveniente.

TAREA

Escriba el código que le da una cadena w, emite RUNS (w).

Idiomas e insumos

Puede usar cualquier idioma que desee y tomar la cadena de entrada en la forma que sea más conveniente. Sin embargo, debe proporcionar un programa completo y debe mostrar un ejemplo de su código ejecutándose en la entrada de ejemplo.

Pyth, 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

Banco de pruebas

CJam, 66

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

Pruébalo en línea

Breve explicacion:

El algoritmo funciona en 4 pasos (los primeros 3 de ellos corresponden a los 3 bloques principales que puede observar):

1. Encuentre todos los pares [índice de longitud] que corresponden a una subcadena duplicada (como aba aba aaacaacac); Estas son partes de carreras.
2. Concatenar pares que forman parte de la misma ejecución, es decir, índices consecutivos y la misma duración / período.
3. Construya las ejecuciones reales, tomando el índice mínimo y el índice máximo + 2 * longitud - 1.
4. Al final, elimine las ejecuciones duplicadas (que son el mismo intervalo obtenido con un período diferente)

Me gustaría jugar más al golf, así que todo está sujeto a cambios.