Encuentra patrones en cadenas

17

En este desafío, su tarea es localizar subcadenas con una estructura dada.

Entrada

Su entrada será dos cadenas alfanuméricas no vacías, un patrón p y un texto t . La idea es que cada carácter de prepresenta una subcadena contigua no vacía tque ocurre una al lado de la otra, y prepresenta su concatenación. Los caracteres idénticos corresponden a subcadenas idénticas; por ejemplo, el patrón aarepresenta cualquier cuadrado no vacío (una cadena obtenida mediante la concatenación de una cadena más corta). Por lo tanto, el patrón aapuede coincidir con la subcadena byebye, con cada acoincidencia bye.

Salida

Si el texto tcontiene una subcadena que pcoincide, entonces su salida será esa subcadena, con dos puntos :insertados entre las cadenas que corresponden a los caracteres de p. Por ejemplo, si tenemos t = byebyenowy p = aa, entonces bye:byees un resultado aceptable. Puede haber varias opciones para la subcadena coincidente, pero solo generará una de ellas.

Si tno contiene una subcadena coincidente, su salida será una cara triste :(.

Reglas y aclaraciones

Diferentes caracteres de ppueden corresponder a subcadenas idénticas, por lo que p = abapueden coincidir con la cadena AAA. Tenga en cuenta que los caracteres deben corresponder a cadenas no vacías; en particular, si pes más largo que t, la salida debe ser :(.

Puede escribir un programa completo o una función, y también puede cambiar el orden de las dos entradas. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Dado en el formato pattern text -> output. Tenga en cuenta que pueden existir otros resultados aceptables.

a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
Zgarb
fuente
1
¿El powerset de todas las subcadenas? ¡Por qué no!
orlp
1
@orlp Es solo O(2^((n * (n + 1))/2)): P
ThreeFx
¿Qué significa un dígito en la cadena del patrón?
feersum
@feersum Es un personaje, por lo que es esencialmente el mismo que cualquier otro personaje.
ThreeFx
@ThreeFx No estoy seguro porque el primer párrafo se refiere solo a "letras" en el patrón.
feersum

Respuestas:

6

Python, 207 bytes

import re
h=lambda x:"a"+str(ord(x))
def g(a,b):
 c,d="",set()
 for e in a:
  c+=["(?P<"+h(e)+">.+)","(?P="+h(e)+")"][e in d]
  d.add(e)
 f=re.search(c,b)
 return f and":".join(f.group(h(e))for e in a)or":("

Llamar con g(pattern, string)

Utiliza el remódulo para hacer la mayor parte del trabajo.

El numero uno
fuente
1

JavaScript (SpiderMonkey) (ES5.1), 198 bytes

Desde que ES6 se lanzó en junio de 2015, publico la versión ES5.1 del código junto con el equivalente ES6, pero declaro la versión ES5.1 como la respuesta principal.

Partido codicioso, por lo que el primer caso devuelve "No" en lugar de "N".

function(a,b){c=[o="indexOf"];r=a.split("");return(m=RegExp(r.map(function(i){return(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")}).join("")).exec(b))?r.map(function(x){return m[c[o](x)]}).join(":"):":("}

Pruébalo en línea!

JavaScript (Node.js) (ES6), 141 bytes

a=>b=>(c=[o="indexOf"],r=[...a],m=RegExp(r.map(i=>(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")).join``).exec(b))?r.map(x=>m[c[o](x)]).join`:`:":("

Pruébalo en línea!

Toma los argumentos en la sintaxis curry: f(a)(b)

Explicación (y sin golf):

function matchPattern(a, b) {                   // Main function
 var c = ["indexOf"];                           // Array used for the capturing groups
 var r = [...a];                                // Split the pattern first
 var m = RegExp(r.map(function(i) {             // Create the regex
  var e = c.indexOf(i);                         // Check if the character is found before
  if (e > 0)                                    // If so
   return "\\" + e;                             // Append the back reference to the regex
  else {                                        // If not
   c.push(i);                                   // Append the character to the array
   return "(.+)";                               // Append a capturing group to the regex
  }             
 }).join("")).exec(b);                          // Execute the regex
 if (m != null)                                 // If the pattern matches the string
  return r.map(function(x) {                    // Replace each letter
   return m[c.indexOf(x)];                      // With the corresponding substring
  }).join(":");                                 // And join them with ":"
 else                                           // If there is no match
  return ":(";                                  // Return ":("
}
Shieru Asakoto
fuente
1

Brachylog , 35 bytes

sᵗ~cᵗXlᵛ∧Xzdz≠ʰ∧Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Pruébalo en línea!

En entradas no muy pequeñas, muy lentas. Realmente no he hecho el sexto caso de prueba, pero no por falta de intentos lentos. (Probablemente debido a la fuerza bruta de cada partición de cada subcadena, comenzando por la más grande y luego verificando si es una coincidencia). Toma la entrada como una lista [pattern,string].

Explicación condensada y dividida:

sᵗ~cᵗX

X es el patrón emparejado con una partición de una subcadena de la cadena de entrada.

lᵛ

El patrón y la partición tienen el mismo número de elementos.

Xzdz≠ʰ

No hay dos pattern char, matched substringpares únicos que compartan un carácter de patrón. Es decir, ningún carácter de patrón se asigna a múltiples subcadenas, aunque varios caracteres de patrón pueden asignarse a una subcadena.

Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

La salida son los elementos de la partición unidos por dos puntos, a menos que no se pueda hacer algo, en cuyo caso es en su :(lugar.

Explicación monolítica:

                                       The input
 ᵗ  ᵗ                                  with its last element replaced with
  ~c                                   a list which concatenates to
s                                      a substring of it
     X                                 is X,
       ᵛ                               the elements of which all have the same
      l                                length.
        ∧                              And,
         X                             X
          z                            zipped
           d                           with duplicate pairs removed
            z                          and zipped back
              ʰ                        has a first element
             ≠                         with no duplicate values.
               ∧                       Furthermore,
                 t                     the last element of
                X                      X
                  ~ṇ                   with its elements joined by newlines
                    {      }ᵐ          where each character of the joined string
                     Ḷ                 is a newline
                      ∧                and
                          |            is replaced with
                       ":"             a colon
                          |            or is passed through unchanged
                             .         is the output.
                              ∨        If doing any part of that is impossible,
                                       the output is
                               ":("    ":(".
Cadena no relacionada
fuente
Ha pasado más de una hora y todavía no ha realizado el sexto caso de prueba ... ¿tal vez en realidad no funciona? Está usando más que su parte de procesador ...
Cadena no relacionada
De acuerdo, o subestimé la complejidad del tiempo de usar múltiples capas de fuerza bruta dura, o esto se rompe de alguna manera, porque todavía no ha hecho el sexto caso de prueba
Cadena no relacionada
Lo he cerrado ahora porque si lleva tres horas, no estoy seguro de cuánto tiempo más estoy dispuesto a esperar
Cadena no relacionada