¡Repite después de mi!

23

Dada una cadena como argumento, genera la longitud de la (s) subcadena (s) repetida (s) más larga (s) que no se superponen o cero si no existe dicha cadena.

Puede suponer que la cadena de entrada no está vacía.

Ejemplos

abcdefabc: la subcadena abcse repite en las posiciones 1 y 7, por lo que el programa debería generar 3

abcabcabcabcab: abcabco bcabcao cabcabse repiten, por lo que el programa debería generar 6 . (la subcadena abcabcabcabtambién se repite, pero las ocurrencias se superponen, por lo que no lo aceptamos).

aaaaaaa: aaase repite en las posiciones 1 y 4, por ejemplo, por lo que el programa debería generar 3

abcda: ase repite, por lo que el programa debería generar 1

xyz: sin cadena repetida → 0

ababcabcabcabcab: debería devolver 6

Este es el , por lo que gana menos bytes.

Arnaud
fuente
1
¿Podría la cuerda estar vacía? Si ese es el caso, ¿se le permitiría generar False en lugar de 0 ?
Dennis
@ Dennis Puede asumir que la cadena no está vacía.
Arnaud

Respuestas:

9

brainfuck, 226 bytes

,[<<<,]+[>>->[[[[>>[>>>]<+<-<[<<<]>>+<-]>[<+>-]>[>>>]<<[>[<+>-]]>[[<+>-]>+[<<<]>
>>-[+>[<<<]<[>+>[->]<<[<]>-]>[<+>>+<-]>>>[>>>]]>>]<]>+[,<<<+]->[<<<]>>>>>+[,+>>>
+]-[>>>]->]<[+<<<]+<<<++[->>>]+>>>->]<[,<<<]<[>>>+<<<-]>+>,>>>]<<.

Formateado:

,[<<<,]
+
[
  for each suffix
  >>->
  [
    for each prefix
    [
      for each suffix
      [
        for each char while no mismatch
        [
          >>[>>>]
          <+<-<[<<<]
          > >+<-
        ]
        >[<+>-]
        >[>>>]
        <<
        [
          mismatch
          >[<+>-]
        ]
        >
        [
          [<+>-]
          >+[<<<]
          >>>-
          [
            match
            +>[<<<]
            <
            [
              >+>[->]
              <<[<]
              >-
            ]
            >[<+> >+<-]
            >>>[>>>]
          ]
          >>
        ]
        <
      ]
      >+[,<<<+]
      ->[<<<]
      >>> >>+[,+>>>+]
      -[>>>]
      ->
    ]
    <[+<<<]
    +<<<++[->>>]
    +>>>->
  ]
  <[,<<<]
  <[>>>+<<<-]
  >+>,>>>
]
<<.

Espera la entrada con o sin una nueva línea final y genera el resultado como un valor de byte .

Pruébalo en línea.

Esto verifica cada prefijo para ver si ocurre más adelante en la cadena, luego corta el primer carácter y repite el proceso hasta que no queden más caracteres.

La cinta se divide en nodos de 3 celdas,

c 0 f

donde ces un carácter de la cadena dada y fes un indicador que puede ser uno, negativo o cero. Los indicadores distintos de cero se colocan entre los dos caracteres que se comparan actualmente, y los negativos se reservan para las celdas después del final del prefijo actual y antes del comienzo del sufijo actual (es decir, antes del índice de la coincidencia potencial actual).

El resultado se almacena a la izquierda de la cadena y se actualiza cada vez que se encuentra una coincidencia.

(La cadena en realidad se procesa en reversa con un \x01adjunto).

Mitch Schwartz
fuente
6

Jalea , 12 bytes

œ-QL€
ŒṖÇ€FṀ

Pruébalo en línea!

Cómo funciona

ŒṖÇ€FṀ  Main link. Argument: s (string)

ŒṖ      Generate all partitions of s.
  ǀ    Apply the helper link to each partition.
    F   Flatten the resulting array of lengths.
     Ṁ  Take the maximum.


œ-QL€   Helper link. Argument: P (partition)

  Q     Yield the elements of P, deduplicated.
œ-      Multiset subtraction; remove exactly one occurrence of each string in P.
   L€   Compute the lengths of the remaining strings. 
Dennis
fuente
1
Todos aclamen a Jelly, ¡el último lenguaje de código de golf!
Nissa
œ-Qes realmente genial
Lynn
5

Perl 6 , 36 bytes

{m:ex/(.*).*$0/.map(*[0].chars).max}

Intentalo

Expandido:

{   # bare block lambda with implicit parameter 「$_」

  m           # match ( implicitly against 「$_」
  :exhaustive # every possible way
  /
    (.*)      # any number of characters ( stored in 「$0」 )
    .*
    $0
  /

  .map(

    *\        # the parameter to Whatever lambda
    [0]\      # the value that was in 「$0」 for that match
    .chars    # the number of characters

  ).max

}
Brad Gilbert b2gills
fuente
5

Retina , 35 32 30 bytes

Muy buen desafío.

M&!`(.*)(?=.*\1)
M%`.
O#^`
G1`

Pruébalo en línea

Explicación:

M&!`(.*)(?=.*\1)    # Prints overlapping greedy substrings occuring more than once
M%`.                # Replace each line with its length
O#^`                # Sort lines by number in reverse
G1`                 # Return the first line
mbomb007
fuente
Puede guardar dos bytes utilizando M%`.como segunda etapa.
Martin Ender
4

JavaScript (ES6), 79 68 66 bytes

f=(s,r,l=s.match(/(.*).*\1/)[1].length)=>s?f(s.slice(1),l<r?r:l):r
<input oninput=o.textContent=f(this.value)><pre id=o>

Editar: Guardado 11 13 bytes gracias a @Arnauld.

Neil
fuente
4

Haskell , 79 bytes

(""%)
(a:b)!(c:d)|a==c=1+b!d
_!_=0
a%c@(e:d)=maximum[a!c,""%d,(a++[e])%d]
_%_=0

Pruébalo en línea!

Asistente de trigo
fuente
2
Parece que el primer argumento de %puede acumular una subsecuencia no contiguo, dando falsos positivos como 2 para aaen axayaa,
XNOR
Lo que dijo @xnor. Creo que la llamada recursiva a%des incorrecta, pero también innecesaria. Lo que también significa que puede usar en maxlugar de maximum.
Ørjan Johansen
1
Creo que cambiar a%dpara ""%darreglarlo.
xnor
Ah, claro, todavía se necesita (y suena) cuando aestá vacío.
Ørjan Johansen
1
Creo que sum[1|(x,y)<-zip a c,x==y]se puede usar en lugar de a!c.
Laikoni
2

JavaScript, 120

function r(a,b,m){return b=-~b,t=a.slice(0,b),n=a.indexOf(t,b),m=b>m&&!~n?m:b,a!=t&&r(a,b,m)||(a?r(a.slice(1),m,m):~-m)}
C5H8NNaO4
fuente
2

Casco , 11 bytes

L►L§fo↓2`xQ

Pruébalo en línea!

Nota: Husk es más nuevo que este desafío.

Explicación

L►L§fo↓2`xQ  Implicit input, say x = "ababc"
          Q  Nonempty substrings: ["a","b","ab",..,"ababc"]
    f        Keep those that satisfy this:
              Take s = "ab" as an example.
   §    `x    Split x along s: ["","","c"]
     o↓2      Drop the first two pieces: ["c"]
              This is truthy (i.e. nonempty).
             Result is ["a","b","ab","a","b","ab"]
 ►L          Take element with maximal length: "ab"
             If the list is empty, "" is used instead.
L            Length: 2
Zgarb
fuente
1

Mathematica, 75 65 bytes

10 bytes guardados debido a @JingHwan Min .

Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&

Función anónima. Toma una cadena como entrada y devuelve un número como salida.

LegionMammal978
fuente
No creo que necesites el principio y el final BlankNullSequence (___)cuando Overlaps->Allesté allí. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&estaría bien
JungHwan Min
@JungHwanMin Gracias, lo estaba confundiendo con StringReplace: P
LegionMammal978
1

Pyth - 16 bytes

Necesito jugar golf convirtiendo todas las cuerdas a longitudes y encontrando el máximo.

eSlM+ksmft/dTd./

Test Suite .

Maltysen
fuente
1

Clojure, 112 bytes

#(apply max(for[R[(range(count %))]j R i R](let[[b e](split-at i(drop j %))](if((set(partition i 1 e))b)i 0)))))

realiza un bucle dos veces sobre los números 0para n - 1( nsiendo la longitud de la cadena), suelta jcaracteres y divide el resto en partes "iniciales" y "finales". Crea un conjunto de todas las subcadenas ede longitud by lo utiliza como una función para verificar si bse encuentra desde allí. Devuelve la longitud de bsi se encuentra y 0 de lo contrario, devuelve el máximo de estos valores.

Sería interesante ver una versión más corta.

NikoNyrh
fuente
1

Retina , 24 bytes

L$v`(.*).*\1
$.1
N`
G-1`

Pruébalo en línea!

Un calentamiento para mí para aprender las nuevas características de Retina 1.

Explicación

L$v`(.*).*\1
$.1

Una etapa de Lista, esto devuelve todas las coincidencias para la expresión regular (.*).*\1, que coincide con cualquier patrón de la forma "ABA", donde A y B son dos subcadenas arbitrarias (posiblemente vacías). Las opciones adicionales dadas a esta etapa son v, que considera coincidencias superpuestas, y $que aplica una sustitución a cada una de las coincidencias antes de devolverla: la sustitución se indica en la segunda línea y corresponde a la longitud ( .) del primer grupo de captura ( que sería la subcadena "A" en el ejemplo anterior).

N`

Ahora tenemos todas las longitudes de subcadenas repetidas, esta etapa simplemente las ordena en orden numérico, desde la más corta hasta la más larga.

G-1`

Finalmente, esta etapa grep ( G) mantiene solo el último -1resultado ( ), que es la longitud de la subcadena repetida más larga.

León
fuente
0

Javascript, 165 bytes

function a(s){var l=s.length/2,z=1,f='';while(z<=l){var t=s.substr(0,z),c=0;for(var i=0;i<s.length;i++){if(s.substr(i,z)===t){c++;if(c>1){f=t}}}z++}return f.length}

Casos de prueba

console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3
Lalith Prasad
fuente
2
Bienvenido a Programming Puzzles & Code Golf. Desafortunadamente, esto devuelve 2 para la entrada ababcabcabcabcab, pero la cadena cabcabse repite.
Dennis