Encuentra la cadena original, sin la repetición sin la repetición en el medio

25

A veces sucede que mientras escribo una oración, me distraigo y termino escribiendo el mismo par de palabras dos veces, dos veces seguidas.

Para asegurarse de que otras personas no se molesten por esto, su tarea es escribir un programa que resuelva este problema.

Tarea

Dada una cadena de entrada (si es importante para su idioma, puede suponer una entrada ASCII solo que no contiene saltos de línea) str, que contiene en algún lugar en el medio una subcadena que ocurre dos veces en sucesión inmediata, devuelva la cadena con una instancia de este subcadena eliminada.

En el caso de múltiples posibilidades, devuelva la respuesta más corta posible (es decir, elija la subcadena repetida consecutiva más larga y elimine esa).

En el caso de múltiples subcadenas repetitivas consecutivas de igual longitud, elimine la primera (es decir, la primera que se encuentre al leer la cadena de adelante hacia atrás).

Puede suponer que la entrada es correcta (es decir, siempre contiene una subcadena repetida consecutiva), lo que podría ayudar a reducirla.


Ejemplos

  1. Entrada: hello hello world-> Salida: hello world.
  2. Entrada: foofoo-> Salida: foo. (Entonces: Sí, la cadena solo puede consistir en la parte repetida dos veces).
  3. Entrada: aaaaa-> Salida: aaacomo la subcadena consecutiva más larga está aquí aa.
  4. Entrada: Slartibartfast-> Esta no es una entrada válida, ya que no contiene una subcadena repetida consecutiva, por lo que no necesita manejar este caso.
  5. Entrada: the few the bar-> Esta es otra entrada no válida, ya que la parte que se repite debe seguir inmediatamente a la parte original. En este caso, they theestán separados por otra cosa intermedia, por lo que esta entrada no es válida.
  6. Entrada: ababcbc-> Salida: abcbc. Las dos subcadenas repetidas consecutivas más largas posibles son aby bc. Como abse encontró anteriormente en la cadena, esta es la respuesta correcta.
  7. Entrada: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Salida: Buffalo buffalo buffalo buffalo Buffalo buffalo. (El reemplazo realizado debe ser sensible a mayúsculas y minúsculas).
  8. Entrada: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.-> Salida: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Solo se elimina la subcadena repetida consecutiva más larga.

Su código debe ser lo más corto posible, ya que es , por lo que gana la respuesta más corta en bytes. ¡Buena suerte!

Qqwy
fuente
@manatwork Al tomar la primera oración, que es Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.como entrada, la salida debería ser Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Solo se elimina la duplicación encontrada más larga.
Qqwy
1
Sugiero agregar una prueba que tenga dos reemplazos posibles, donde el segundo es más largo que el primero. Sospecho que la mayoría de las respuestas no pasarán esa :)
Aross
El caso de prueba de @aross 8 es exactamente eso :)
Qqwy
A menos que yo y mi código de prueba estén equivocados, solo hay una cadena repetida allí.
aross
@aross hay un doble penhappens
Qqwy

Respuestas:

8

Perl 6 , 40 bytes

{.subst: m:ex/(.*))>$0/.max(*.chars),''}

Intentalo

{
  .subst:             # substitute


    m                 # match
    :exhaustive
    /
      ( .* )          # any number of chars

      )>              # don't include the following in what is returned

      $0              # the first match again
    /.max( *.chars ), # find the first longest submatch


    ''                # substitute it with nothing
}
Brad Gilbert b2gills
fuente
8

Retina , 35 33 bytes

El recuento de bytes asume la codificación ISO 8859-1.

(?=(.+)(\1.*))
$2¶$`
O$#`
$.&
G1`

Pruébalo en línea!

Explicación

Dado que los motores regex buscan coincidencias de izquierda a derecha, no es trivial encontrar la coincidencia más larga, independientemente de la posición. Se puede hacer con los grupos de equilibrio de .NET, pero el resultado es bastante desagradable:

1`((.)+)\1(?<=(?!.*((?>(?<-2>.)+).+)\3)^.*)
$1

Así que pensé que trataría de evitar eso haciendo uso de algunas otras funciones de Retina.

(?=(.+)(\1.*))
$2¶$`

Comenzamos aplicando esencialmente todas las sustituciones posibles, una en cada línea. Para hacer esto, hacemos coincidir la posición frente a una coincidencia (en lugar de la coincidencia misma), para permitir coincidencias superpuestas. Esto se hace poniendo la expresión regular real en una anticipación. Esa búsqueda anticipada luego captura el resto excepto el duplicado que queremos eliminar en el grupo 2. Reescribimos el grupo 2 (eliminando el duplicado), un salto de línea, y luego toda la entrada hasta la coincidencia, que nos da básicamente una nueva línea para ser sustituido

Al final tendremos una línea para cada partido, con el correspondiente duplicado eliminado. Al final, también habrá una entrada completa nuevamente sin ninguna sustitución.

Ahora que tenemos todas las sustituciones posibles, queremos el resultado más corto (que corresponde a la repetición eliminada más larga).

O$#`
$.&

Entonces, primero ordenamos las líneas por longitud.

G1`

Y luego solo mantenemos la primera línea.

Martin Ender
fuente
¡Vaya, esa técnica de reemplazo es realmente inteligente!
Leo
6

Jalea , 22 19 bytes

-2 bytes gracias a Dennis (evite una inversión de argumento, elimine incrementos sutilmente redundantes)

ẋ2³wȧ+¥J
ẆÇ€LÐṀḢṬœp

Pruébalo en línea!

Programa completo (se ha encontrado un error al ÐṀno actuar con el arity correcto sobre las díadas, que se solucionará pronto; aunque no estoy seguro de que pueda hacer un código más corto aquí).

¿Cómo?

Encuentra el primero de los segmentos más largos de la entrada de modo que exista una repetición en la entrada y lo elimina de la entrada.

ẋ2³wȧ+¥J - Link 1, removal indices for given slice if valid, else 0: slice, x
ẋ2       - repeat x twice, say y
  ³      - program input: s
   w     - index of first occurrence of y in s (1-based) or 0, say i
       J - range(length(x)): [1,2,3,...,length(x)]
      ¥  - last two links as a dyad
    ȧ    -     and (non-vectorising)
     +   -     addition: [1+i,2+i,3+i,...,length(x)+i] or 0
         - note: no need to decrement these since the last index will be the 1st index
         - of the repetition (thanks to Dennis for spotting that!)

ẆÇ€LÐṀḢṬœp - Main link: string, s
Ẇ          - all sublists of s (order is short to long, left to right, e.g. a,b,c,ab,bc,abc)
 Ç€        - call the last link (1) as a monad for €ach
    ÐṀ     - filter by maximal
   L       -     length
      Ḣ    - head: get the first (and hence left-most) one
       Ṭ   - untruth: make a list with 1s at the indexes given and 0s elsewhere
        œp - partition s at truthy indexes of that, throwing away the borders
           - implicit print
Jonathan Allan
fuente
6

JavaScript (ES6), 81 74 bytes

f=
s=>s.replace(/(?=(.+)\1)/g,(_,m)=>r=m[r.length]?m:r,r='')&&s.replace(r,'')
<input oninput=o.textContent=f(this.value)><pre id=o>

Editar: Guardado 7 bytes al robar el m[r.length]truco de @ Arnauld .

Neil
fuente
5

PowerShell , 87 bytes

param($s)([regex](([regex]'(.+)\1'|% *hes $s|sort L*)[-1]|% Gr*|% V*)[1])|% Re* $s '' 1

Pruébalo en línea! (todos los casos de prueba)

Explicación

Comenzando desde adentro básicamente, corremos Matchescon la (.+)\1expresión regular, para devolver todos los objetos coincidentes para la cadena especificada. La expresión regular coincide con cualquier secuencia de caracteres seguida sola.

Luego, los objetos de coincidencia resultantes se canalizan sortpara ser ordenados por su Lengthpropiedad (acortados a comodín). Esto da como resultado una serie de coincidencias ordenadas por longitud, ascendentes, por lo que debe indexarse [-1]para obtener el último elemento (el más largo). Sin embargo, el valor de esa coincidencia es la coincidencia, no el grupo, por lo que incluye la repetición, por lo que recuperamos el objeto Grupo ( |% Gr*) y luego el valor de ese ( |% V*) para obtener la cadena repetida más grande. La cosa es que el objeto de grupo es en realidad una matriz porque el grupo 0 siempre es la coincidencia, pero quiero el grupo real (1), por lo que el valor resultante es en realidad el valor s , por lo tanto, la indexación para obtener el segundo elemento [1]. Este valor se convierte en un objeto regex y luego elReplaceSe llama al método contra la cadena original, reemplazándolo por nada, y solo se reemplaza la primera coincidencia ( |% Re* $s '' 1).

briantista
fuente
5

Haskell , 101 bytes

La función principal es f, toma y devuelve a String.

l=length
a=splitAt
f s|i<-[0..l s-1]=[p++t|n<-i,(p,(r,t))<-fmap(a$l s-n).(`a`s)<$>i,r==take(l r)t]!!0

Pruébalo en línea!

Cuando empecé esto, he importado Data.Listy usado maximum, tails, initsy isPrefixOf. De alguna manera eso se convirtió en esto. Pero aún así solo logré eliminar 11 bytes ...

Notas

  • splitAt/ adivide una cadena en un índice dado.
  • s es la cadena de entrada.
  • ies la lista de números [0 .. length s - 1], -1es para evitar que se splitAtdivida al final si se le da un índice demasiado grande.
  • nes length smenos el objetivo de longitud actual para la parte repetida, se elige de esa manera para que no tengamos que usar dos listas de números y / o la sintaxis detallada de lista decreciente.
  • p, rY tson una división de tres vías de s, con rel destinados repiten parte. El fmapno utiliza el (,) String Functorde evitar una variable para una división intermedia.
  • !!0 selecciona el primer elemento de la lista de coincidencias.
Ørjan Johansen
fuente
4

Jalea , 23 21 bytes

ṚẆUẋ€2ẇÐf¹ṪðLHḶ+w@Ṭœp

Gracias a @JonathanAllan por su Ṭœpidea que ahorró 2 bytes.

Pruébalo en línea!

Dennis
fuente
4

Mathematica, 63 60 59 bytes

4 bytes guardados debido a Martin Ender .

#&@@StringReplaceList[#,a__~~a__->a]~SortBy~{StringLength}&

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

LegionMammal978
fuente
Esto no parece funcionar en el ejemplo 6 - ~SortBy~StringLengthordena las cadenas alfabéticamente si sus longitudes son las mismas ...
No es un árbol
1
@ LegionMammal978 La solución más corta es mantener SortByy envolver StringLengthen una lista para obtener una ordenación estable.
Martin Ender
3

JavaScript (ES6), 70 bytes

s=>s.replace(s.match(/(.+)(?=\1)/g).reduce((p,c)=>c[p.length]?c:p),'')

Casos de prueba

Arnauld
fuente
Falla aaaabaaab, pero buen uso de reduce.
Neil
2

Esto debería ser un comentario, pero no tengo suficientes reputaciones para comentar. Solo quiero decirle a @Neil que su código se puede reducir a 77 bytes. No es necesario utilizar la aserción directa en regex. Aquí está la versión reducida:

s=>s.replace(/(.+)\1/g,(_,m)=>(n=m.length)>l&&(l=n,r=m),l=0)&&s.replace(r,'')
TRÓLL
fuente
2
Hola y bienvenidos a PPCG! ¡Puede enviar esto como su propia respuesta de JavaScript! Si lo desea, puedo editar su publicación y mostrarle cómo debería verse.
NoOneIsHere
2
Necesito usar la afirmación directa para tratar el caso de coincidencias superpuestas. aababes el ejemplo más corto de dónde falla su sugerencia.
Neil
0

C #, 169 bytes

(s)=>{var x="";for(int i=0;i<s.Length-2;i++){for(int l=1;l<=(s.Length-i)/2;l++){var y=s.Substring(i,l);if(s.Contains(y+y)&l>x.Length)x=y;}}return s.Replace(x+x,x);}

Explicación

(s) => {                // Anonymous function declaration    
    var x = "";         // String to store the longest repeating substring found
    for (int i = 0; i < s.Length - 2; i++) {               // Loop through the input string
        for (int l = 1; l <= (s.Length - i) / 2; l++) {    // Loop through all possible substring lengths
            var y = s.Substring(i, l);
            if (s.Contains(y + y) & l > x.Length) x = y;   // Check if the substring repeats and is longer than any previously found
        }
    }
    return s.Replace(x + x, x);    // Perform the replacement
}

Este es el enfoque de la fuerza bruta: pruebe todas las subcadenas posibles hasta que encontremos la subcadena más larga que se repite. Indudablemente, Regex es más eficiente, pero tratar con Regex en C # tiende a ser bastante detallado.

Extragorey
fuente
Bienvenido a PPCG! Todas las respuestas deben ser programas completos o funciones invocables , no estoy seguro de fragmentos con entradas en variables codificadas. Además, muestre la versión del código que realmente contó con todos los espacios en blanco innecesarios eliminados. Siempre puede incluir la versión más legible con sangría además de la versión totalmente golfizada.
Martin Ender
0

PHP, 84 82 bytes

Nota: utiliza la codificación IBM-850.

for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;

Corre así:

echo 'hello hello world' | php -nR 'for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;';echo
> hello world

Explicación

for(
  $l=strlen($argn);   # Set $l to input length.
  --$l   &&           # Decrement $l each iteration until it becomes 0.
  !$r=preg_filter(    # Stop looping when preg_filter has a result
                      # (meaning a successful replace).
    "#(.{0$l})\g-1#", # Find any character, $l times (so the longest
                      # match is tried first), repeated twice.
    ~█╬,              # Replace with $1: first capture group, removing the
                      # duplicate.
    $argn,
    1                 # Only replace 1 match.
  );
);
echo$r;               # Print the result of the (only) successful
                      # search/replace, if any.

Ajustes

  • Se guardaron 2 bytes porque no hay una longitud mínima de la subcadena repetida
aross
fuente