Dada una lista de cadenas, reemplace cada cadena por una de sus subcadenas no vacías, que no es una subcadena de ninguna de las otras cadenas de la lista y lo más corta posible.

Ejemplo

Teniendo en cuenta la lista ["hello","hallo","hola"], "hello"debe ser reemplazado por igual "e"ya que esta subcadena no está contenida en "hallo"e "hola"y es lo más corta posible. "hallo"podría ser reemplazado por cualquiera de "ha"o "al"y "hola"por cualquiera de "ho", "ol"o "la".

Reglas

• Puede suponer que las cadenas no estarán vacías y solo contendrán caracteres alfabéticos del mismo caso.
• Puede suponer que existe una subcadena para cada cadena de la lista, es decir, ninguna cadena de la lista será una subcadena de ninguna de las otras cadenas.
• La entrada y salida pueden estar en cualquier formato razonable.
• Este es el código de golf , así que trate de usar la menor cantidad de bytes posible en el idioma que elija.

Casos de prueba

Solo se proporciona una salida posible para la mayoría de los casos.

["ppcg"] -> ["p"] (or ["c"] or ["g"])
["hello","hallo","hola"] -> ["e","ha","ho"]
["abc","bca","bac"] -> ["ab","ca","ba"]
["abc","abd","dbc"] -> ["abc","bd","db"]
["lorem","ipsum","dolor","sit","amet"] -> ["re","p","d","si","a"]
["abc","acb","bac","bca","cab","cba"] -> ["abc","acb","bac","bca","cab","cba"]

^{Relacionado: Subcadena de identificación más corta : idea similar, pero reglas más complicadas y formato engorroso.}

Jalea ,  12  9 bytes

Ẇ€ŒpẇþÞ⁸Ḣ

Pruébalo en línea! O vea el conjunto de pruebas (tarda ~ 35s)

Python 2 , 116 bytes

def f(a):g=lambda s,S:s not in`set(a)-{S}`[3:]and min(s,g(s[1:],S),g(s[:-1],S),key=len)or S;return[g(s,s)for s in a]

Pruébalo en línea!

Pyth , 12 bytes

mhf!ts}LTQ.:

Pruébalo aquí!

Cómo funciona

Básicamente filtra las subcadenas de cada una que solo ocurren en una de las cadenas de la lista (es decir, es única para esa cadena) y obtiene la primera.

mhf!ts}LTQ.:     Full program, Q=eval(stdin_input())
m         .:     Map over Q and obtain all the substrings of each.
  f              And filter-keep those that satisfy (var: T)...
      }LTQ       ... For each string in Q, yield 1 if it contains T, else 0.
   !ts           ... Sum the list, decrement and negate. 
 h               Head. Yields the first valid substring, which is always the shortest.

Prólogo (SWI) , 175 163 bytes

S/L/R:-sub_string(S,_,L,_,R).
[H|T]+[I|R]:-string_length(H,L),between(1,L,X),H/X/I,T+R.
R+R.
L-R:-L+R,forall(member(E,L),findall(_,(member(F,R),\+ \+ E/_/F),[_])).

Pruébalo en línea!

La mayoría de las cosas aquí deberían ser bastante obvias, pero:

Explicación

Firmas: ( += entrada, ?= opcional, -= salida, := expresión)

• sub_string(+String, ?Before, ?Length, ?After, ?SubString)
• string_length(+String, -Length)
• member(?Elem, ?List)
• between(+Low, +High, ?Value)
• findall(+Template, :Goal, -Bag)
• forall(:Cond, :Action)

\+ \+es justo not not(es decir, convierte una coincidencia en booleana (en este caso, evita que coincida con ambas ps por ppcgseparado))

APL (Dyalog) , 25 bytes

Gracias por guardar un byte

⊃¨1↓≢~⍨/(,⍨(,∘↑⍳∘≢,/¨⊂)¨)

Pruébalo en línea!

J , 30 29 25 bytes

1(|:(0{-.&,)"_1]\.)<\\.&>

Pruébalo en línea!

                   <\\.&>        a 3-dimensional array of substrings
1 |:                             transpose each matrix to sort the substrings by length
1              ]\.               all choices where one word is missing
    (0{-.&,)"_1                  for every matrix, flatten, remove substrings
                                  that are present in the corresponding complement,
                                  pick first

Jalea , 10 bytes

Ẇ€ṙƬ1ḟ/Ḣ$€

Pruébalo en línea!

JavaScript (ES6), 93 bytes

a=>a.map(s=>(L=s.length,g=n=>a.every(S=>S==s|!~S.search(u=s.substr(n%L,n/L+1)))?u:g(n+1))(0))

Pruébalo en línea!

¿Cómo?

Para cada cadena s de longitud L en la matriz de entrada a [] y comenzando con n = 0 , usamos la función recursiva g () para generar todas las subcadenas u de s con:

u = s.substr(n % L, n / L + 1)

Por ejemplo, con s = "abc" y L = 3 :

 n | n%L | floor(n/L+1) | u
---+-----+--------------+-------
 0 |  0  |       1      | "a"
 1 |  1  |       1      | "b"
 2 |  2  |       1      | "c"
 3 |  0  |       2      | "ab"
 4 |  1  |       2      | "bc"
 5 |  2  |       2      | "c"
 6 |  0  |       3      | "abc"
 7 |  1  |       3      | "bc"
 8 |  2  |       3      | "c"

Algunas subcadenas se generan varias veces, pero no importa. Lo importante es que todas las subcadenas de longitud N se hayan generado antes de cualquier subcadena de longitud N + 1 .

Nos detenemos el proceso tan pronto como u no se puede encontrar en cualquier otra cadena de S en un [] , que está garantizado que ocurra cuando u == s en el peor de los casos, de acuerdo con la regla desafío # 2:

ninguna cadena en la lista será una subcadena de ninguna de las otras cadenas

Por lo tanto, en el ejemplo anterior, los pasos 7 y 8 en realidad nunca se procesarán.

Potencia Shell , 107 bytes

($a=$args)|%{$(for($i=0;$i++-lt($g=($s=$_)|% Le*)){0..($g-$i)|%{$s|% s*g $_ $i}|?{!($a-match$_-ne$s)}})[0]}

Pruébalo en línea!

Explicación

Para cada cadena suministrada (y asigne toda la matriz a $a):

• Haga un forbucle sobre cada longitud de subcadena (basada en 1) de la cadena (asignando la cadena $sy la longitud a $g)
• Para cada longitud ( $i):
  • Haga un bucle de índice, de 0 a longitud - $i, luego para cada índice:
    • Obtener la subcadena de la cadena actual ( $s) en la posición $_(índice) y de longitud$i
    • Pase esa subcadena a Where-Object( ?) y devuélvala si:
      • El subconjunto de array ( $a) que no contiene la cadena actual $s, no tiene una coincidencia para la subcadena actual$_

De vuelta al nivel de la cadena, tenemos todas las subcadenas de esta cadena que no se encontraron en las demás, así que tome la primera [0]ya que solo necesitamos una de ellas, luego continúe con la siguiente cadena.

C # (compilador interactivo de Visual C #) , 149 bytes

a=>a.Select(s=>{var t=s;for(int j=0,k,l=s.Length;j++<l;)for(k=-1;j+k++<l;)if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())j=k=l;return t;})

Pruébalo en línea!

Menos golf ...

// a is an input array of strings
a=>
  // iterate over input array   
  a.Select(s=>{
    // t is the result string
    var t=s;
    // j is the substring length
    for(int j=0,k,l=s.Length;j++<l;)
      // k is the start index
      for(k=-1;j+k++<l;)
        // LINQ query to check if substring is valid
        // the tested string is collected in t
        if(!a.Where(u=>s!=u&u.Contains(t=s.Substring(k,j))).Any())
          // break loops
          j=k=l;
    // return result
    return t;
  })