Biorąc pod uwagę listę ciągów, zamień każdy ciąg na jeden z niepustych podciągów, który nie jest podciągiem żadnego z pozostałych ciągów na liście i tak krótki, jak to możliwe.

Przykład

Biorąc pod uwagę listę ["hello","hallo","hola"], "hello"należy zastąpić tylko "e"jako ten podciąg nie jest zawarta w "hallo"a "hola"i to możliwie jak najkrótszy. "hallo"mogą być zastąpione przez jedną "ha"lub "al"i "hola"dowolną "ho", "ol"lub "la".

Zasady

• Możesz założyć, że ciągi będą niepuste i będą zawierały tylko znaki alfabetu tego samego przypadku.
• Możesz założyć, że taki podciąg istnieje dla każdego ciągu na liście, tzn. Żaden ciąg na liście nie będzie podciągiem żadnego z pozostałych ciągów.
• Dane wejściowe i wyjściowe mogą mieć dowolny rozsądny format.
• To jest golf golfowy , więc spróbuj użyć jak najmniej bajtów w wybranym języku.

Przypadki testowe

W większości przypadków podana jest tylko jedna możliwa wydajność.

["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"]

^{Powiązane: Najkrótsze identyfikujące podciąg - podobny pomysł, ale bardziej zaangażowane reguły i kłopotliwy format.}

Galaretka ,  12  9 bajtów

Ẇ€ŒpẇþÞ⁸Ḣ

Wypróbuj online! Lub zobacz pakiet testowy (zajmuje ~ 35s)

Python 2 , 116 bajtów

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]

Wypróbuj online!

Pyth , 12 bajtów

mhf!ts}LTQ.:

Wypróbuj tutaj!

Jak to działa

Zasadniczo filtruje podciągi każdego z nich, które występują tylko w jednym z ciągów na liście (to znaczy, jest unikalny dla tego ciągu) i pobiera pierwszy.

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.

Prolog (SWI) , 175 163 bajtów

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),[_])).

Wypróbuj online!

Większość rzeczy tutaj powinna być dość oczywista, ale:

Wyjaśnienie

Podpisy: ( += wejście, ?= opcjonalne, -= wyjście, := wyrażenie)

• 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)

\+ \+jest po prostu not not(tzn. konwertuje dopasowanie na wartość logiczną (w tym przypadku zapobiega dopasowywaniu obu ps ppcgosobno))

APL (Dyalog) , 25 bajtów

Dzięki ngn za zapisanie jednego bajtu

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

Wypróbuj online!

J , 30 29 25 bajtów

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

Wypróbuj online!

                   <\\.&>        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

Galaretka , 10 bajtów

Ẇ€ṙƬ1ḟ/Ḣ$€

Wypróbuj online!

JavaScript (ES6), 93 bajty

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))

Wypróbuj online!

W jaki sposób?

Na każdy łańcuch y o długości L w tablicy wejścia A [] i wychodząc z n = 0 , używamy funkcji rekurencyjnej g (), w celu wytworzenia wszystkich podciągów U of s z:

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

Na przykład s = „abc” i 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"

Niektóre podciągi są generowane kilka razy, ale to nie ma znaczenia. Co ważne, wszystkie podciągi o długości N zostały wygenerowane przed podciągami o długości N + 1 .

Zatrzymamy proces tak szybko, jak u nie można znaleźć w żadnym innym strun S w A [] , która jest gwarancją zdarzyć, gdy u == y w najgorszym przypadku, zgodnie z zasadą challenge # 2:

żaden ciąg na liście nie będzie podciągiem żadnego z pozostałych ciągów

Dlatego w powyższym przykładzie kroki 7 i 8 faktycznie nigdy nie zostaną przetworzone.

PowerShell , 107 bajtów

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

Wypróbuj online!

Wyjaśnienie

Dla każdego dostarczonego ciągu (i przypisz całą tablicę $a):

• Wykonaj forpętlę na każdej długości podciągu (w oparciu o 1) łańcucha (przypisując sam łańcuch $si długość do $g)
• Dla każdej długości ( $i):
  • Utwórz pętlę indeksu od 0 do długości - $ia następnie dla każdego indeksu:
    • Uzyskaj podciąg bieżącego łańcucha ( $s) w pozycji $_(indeks) i długości$i
    • Przekaż to podciąg do Where-Object( ?) i zwróć, jeśli:
      • Podzbiór array ( $a), który nie zawiera bieżącego ciągu $s, nie ma dopasowania do bieżącego podciągu$_

Z powrotem na poziomie łańcucha, mamy wszystkie podciągi tego łańcucha, które nie zostały znalezione w innych, więc weź pierwszy, [0]ponieważ potrzebujemy tylko jednego z nich, a następnie przejdź do następnego.

C # (interaktywny kompilator Visual C #) , 149 bajtów

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;})

Wypróbuj online!

Mniej golfa ...

// 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;
  })