Calcular las corridas de una cadena

11

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.


fuente
44
Buen desafío, pero ¿hay alguna buena razón para anular las funciones predeterminadas y no permitir?
Martin Ender
@ MartinEnder Es solo mi preferencia. Facilita a las personas simplemente copiar y pegar código y probarlo ellos mismos, lo que a su vez hace que las respuestas sean más interesantes para más personas.
44
Pero eso también causa una gran cantidad de código indirecto, lo que hace que la competencia sea injusta para los idiomas con una sintaxis detallada. No estaría de golf en Java, por ejemplo, si tuviera que escribir class A{public static ...}cada vez que quería código de golf
Bassdrop Cumberwubwubwub
@BassdropCumberwubwubwub Puedo ver que hay pros y contras. Me pasa a pesar los profesionales más fuertemente. Creo que es más interesante comparar la longitud de las respuestas de golf en lenguajes similares en cualquier caso, en lugar de comparar APL con Python, por ejemplo.
"una ejecución es máxima si no está completamente contenida dentro de una ejecución más grande" pero en su primer ejemplo, [7,8] está totalmente contenida dentro de [2,8]. ¿O estás hablando estrictamente de ejecuciones que repiten la misma subcadena?
Aditsu renunció porque SE es MAL

Respuestas:

2

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

Anders Kaseorg
fuente
Obtengo "[[3, 5], [6, 8], [0, 4], [1, 8]]" de "atattatt". ¿Representa [3,5] "tt"? Sería genial si pudieras explicar el algoritmo que has usado también a un alto nivel.
@Lembik Sí, [i, j]representa la partida rebanada entre caracteres (0 reajustables) i-1y iy termina entre los personajes j-1y j. Esta es la convención estándar en Pyth y en la mayoría de los idiomas sanos, como debería ser (ver aquí y aquí ).
Anders Kaseorg
Excelente. ¿Es posible describir su solución intuitivamente? Lamentablemente, no puedo realizar ingeniería inversa desde la descripción de su código.
1
@Lembik Supongamos que estamos buscando corridas del período d. Encontramos todas las ubicaciones donde el carácter i coincide con el carácter i + d. Luego encontramos corridas de al menos d ubicaciones consecutivas. Repita para todos los d. Tenemos que deduplicar al final porque el período real podría haber sido solo un divisor de d.
Anders Kaseorg
1

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.

aditsu renunció porque SE es MALO
fuente
Gracias por esto. ¿Podría explicar el algoritmo que ha utilizado también, por favor?
1
@Lembik ok, actualizado
aditsu se retiró porque SE es MAL