Biorąc pod uwagę (na STDIN, jako argumenty wiersza poleceń lub jako argumenty funkcji) dwa różne niepuste ciągi, znajdź i zwróć najkrótszy ciąg pierwszego ciągu, który nie jest ciągiem drugiego. Jeśli taki podciąg nie istnieje, możesz zwrócić pusty ciąg, zwrócić dowolny ciąg, który nie jest podciągiem oryginalnego ciągu, lub zgłosić wyjątek. Jeśli wracasz z funkcji, możesz również zwrócić null (lub niezdefiniowany, None, itp.) W tym przypadku. Jeśli kilka takich podciągów jest powiązanych w najkrótszym czasie, możesz zwrócić jeden z nich.

Ciągi znaków mogą zawierać dowolne znaki ascii do wydrukowania.

Dane wejściowe podane na STDIN będą podawane z jednym ciągiem w każdej linii. Na żądanie można dodać jedną pustą linię na końcu danych wejściowych.

To jest golf golfowy, więc wygrywa najkrótszy prawidłowy program.

NIEKTÓRE PRZYPADKI TESTOWE

WEJŚCIE:

STRING ONE
STRING TWO

WYNIK:

E

WEJŚCIE:

A&&C
A&$C

WAŻNE PRODUKTY:

&&
&C

WEJŚCIE:

(Dwa losowo generowane ciągi 80-literowe)

QIJYXPYWIWESWBRFWUHEERVQFJROYIXNKPKVDDFFZBUNBRZVUEYKLURBJCZJYMINCZNQEYKRADRYSWMH
HAXUDFLYFSLABUCXUWNHPSGQUXMQUIQYRWVIXGNKJGYUTWMLLPRIZDRLFXWKXOBOOEFESKNCUIFHNLFE

WSZYSTKIE WAŻNE PRODUKTY:

AD
BJ
BR
CZ
DD
EE
ER
EY
EY
FF
FJ
FW
FZ
HE
IJ
IN
IW
JC
JR
JY
KL
KP
KR
KV
LU
MH
MI
NB
NQ
OY
PK
PY
QE
QF
QI
RA
RB
RF
RO
RV
RY
RZ
SW
UE
UH
UN
UR
VD
VQ
VU
WB
WE
WI
WU
XN
XP
YI
YK
YK
YM
YS
YW
YX
ZB
ZJ
ZN
ZV

Brachylog , 23 bajty

:1foh.,{,.[A:B]hs?'~sB}

Działa na starym transpilerze Java. Oczekuje, że dwa ciągi na liście jako dane wejściowe, ujednolica dane wyjściowe z podłańcuchem. Jeśli nie znaleziono żadnego podłańcucha, zwraca false.

Niestety nie zakodowałem jeszcze podzbioru wbudowanego w nowy transpiler Prolog.

Wyjaśnienie

:1f               Find all bindings which satisfy predicate 1 with that binding as input and
                  with the Input of the main predicate as output.
   oh.,           Order that list of bindings, and unify the output with the first one.

{
 ,.[A:B]          Unify the output with the list [A,B]
        hs?       Unify the input with a subset of A
           '~sB   Check that no subset of B can be unified with the input
               }

Python, 119 115 91

lambda a,b:[a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a))if a[m:m+n]not in b][0]

Przypadki testowe:

| Input 1  | Input 2     | Output        |
|----------+-------------+---------------|
| 'abcd'   | 'abc'       |  'd'          |
| 'abcd'   | 'dabc'      |  'cd'         |
| 'abcd'   | 'dcbabbccd' |  'abc'        |
| 'abcdf'  | 'abcdebcdf' |  'abcdf'      |
| 'abc'    | 'abc'       |  (IndexError) |

Pracuję nad tym, aby był krótszy, ale to mój instynkt mózgu. Jeszcze nie bardzo golfista.

Dzięki @ user81655 i @NonlinearFruit za dodatkowe bajty.

Edytuj :

Dang. Próbowałem tego kodu:

def z(a,b):
 for s in [a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a)-n+1)]:
  if s not in b:return s
 return''

Pomyślałem, że jest o kilka bajtów krótszy. Okazuje się, że był o 1 bajt dłuższy niż to, co miałem przed edycją.

Python, 87 86 bajtów

lambda s,t,e=enumerate:[s[i:i-~j]for j,_ in e(s)for i,_ in e(s)if(s[i:i-~j]in t)<1][0]

Jeśli istnieje, zwróci skrajnie lewy ze wszystkich najkrótszych unikalnych podciągów.

Jeśli nie ma unikalnego podłańcucha, zgłaszany jest błąd IndexError .

Przetestuj na Ideone .

Python, 82 bajty

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}
f=lambda s,t:min(g(s)-g(t),key=len)

Zastosowanie: f('A&&C', 'A&$C')-> zwraca'&&'

Podnosi ValueError, jeśli nie ma odpowiedniego podciągu.

Wyjaśnienie:

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}rekurencyjnie tworzy zestaw podciągów z u f=lambda s,t:min(g(s)-g(t),key=len)najkrótszych podciągów z różnicy w zestawie

JavaScript (ES6), 79 bajtów

f=
(a,b)=>[...a].some((_,i,c)=>c.some((_,j)=>b.indexOf(s=a.substr(j,i+1))<0))?s:''

<div oninput=o.textContent=f(a.value,b.value)><input id="a"/><input id="b"/><pre id=o>

Jeśli zwracanie falsejest dopuszczalne, zapisz 2 bajty, używając &&szamiast ?s:''.

Pyth, 11 bajtów

Jwhf!}TJ.:z

Wypróbuj online!

JavaScript (Firefox), 80 bajtów

solution=

a=>b=>[for(_ of(i=0,a))for(_ of(j=!++i,a))if(b.includes(s=a.substr(j++,i)))s][0]

document.write("<pre>"+
[ [ "test", "best" ], [ "wes", "west" ], [ "red", "dress" ] ]
.map(c=>c+": "+solution(c[0])(c[1])).join`\n`)

Test działa tylko w przeglądarce Firefox. Zwraca, undefinedjeśli nie ma podciągu.

Siatkówka , 37 bajtów

M!&`\G(.+?)(?!.*¶.*\1)
O$#`.+
$.&
G1`

Dane wyjściowe są puste, jeśli nie znaleziono poprawnego podłańcucha w A.

Wypróbuj online! (Nieznacznie zmodyfikowano, aby uruchamiało kilka przypadków testowych jednocześnie. Format wejściowy jest faktycznie oddzielony od linii, ale zestawy testów najłatwiej jest napisać z jednym przypadkiem w linii. Środowisko testowe przekształca przestrzeń w kanał przed rozpoczęciem właściwego kodu.)

Wyjaśnienie

M!&`\G(.+?)(?!.*¶.*\1)

Dla każdej możliwej pozycji początkowej w Adopasuj najkrótszy podciąg, który nie pojawia się w B. &Jest dla nakładających się mecze, takie, które rzeczywiście staramy każdą pozycję wyjściową, nawet jeśli jest to mecz dłużej niż jeden znak. W \Ggwarantuje, że nie pominąć żadnej pozycji - w szczególności w ten sposób mamy do przystanku przy wysuw, tak że nie mamy dodatkowe mecze od Bsiebie. Powód, dla którego to nie psuje, jest w rzeczywistości dość subtelny: ponieważ jeśli jest pozycja początkowaA której nie możemy znaleźć żadnego prawidłowego podłańcucha, oznacza to również awarię, która spowoduje, że \Gprzestaniesz sprawdzać dalsze pozycje. Jeśli jednak (z bieżącej pozycji początkowej) wszystkie podciągi pojawią się wB, podobnie jak wszystkie podciągi, które zaczynają się bardziej na prawo od bieżącej pozycji, więc ich odrzucenie nie stanowi problemu (i faktycznie poprawia wydajność).

Ze względu na M!konfigurację wszystkie te mecze zostaną zwrócone ze sceny, połączone z liniami.

O$#`.+
$.&

To sortuje linie poprzedniego wyniku według długości. Odbywa się to poprzez dopasowanie linii do .+. Następnie $aktywuje formę „sortowania według”, dzięki czemu dopasowanie jest zastępowane $.&określaniem kolejności sortowania. $.&Sama zastępuje mecz z jego długości. Na koniec #opcja mówi Retinie, aby sortowała numerycznie (w przeciwnym razie traktowałaby powstałe liczby jako łańcuchy i sortowała je leksykograficznie).

G1`

Wreszcie, po prostu zachowujemy tylko pierwszą linię, używając etapu grep z pustym wyrażeniem regularnym (który zawsze pasuje) i limitem 1.

Perl, 87 85

sub{(grep{$_[1]!~/\Q$_/}map{$}=$_;map{substr($_[0],$_,$})}@}}(@}=0..length$_[0]))[0]}

Jest to anonimowa funkcja, która zwraca pierwsze (według pozycji) najkrótszych podciągów $_[0], które nie występują w $_[1]lub undefjeśli takie podciąg nie istnieje.

Program testowy z ciągami zaczerpniętymi z odpowiedzi @ iAmMortos, przetestowany w Perlu 5.22.1:

#!/usr/bin/perl -l
use strict;
use warnings;

my $f = <see above>;
print $f->('abcd', 'abc');
print $f->('abcd', 'dabc');
print $f->('abcd', 'dcbabbccd');
print $f->('abcdf', 'abcdebcdf');
print $f->('abc', 'abc');

Haskell, 72 bajty

import Data.Lists
a#b=argmin length[x|x<-powerslice a,not$isInfixOf x b]

Przykład użycia: "abcd" # "dabc"-> "cd".

Prosta implementacja: zbuduj wszystkie podciągi ai zachowaj te, które się nie pojawiają b. argminzwraca element listy, który minimalizuje funkcję otrzymują 2nd argument tutaj: length.

Pyth - 9 6 bajtów

h-Fm.:

Wypróbuj online tutaj .

C #, 152 bajty

string f(string a,string b){int x=a.Length;for(int i=1;i<=x;i++)for(int j=0;j<=x-i;j++){var y=a.Substring(j,i);if(!b.Contains(y))return y;}return null;}

Rubinowy, 70 bajtów

Zbiera wszystkie podciągi o określonej długości z pierwszego ciągu, a jeśli istnieje taki, którego nie ma w drugim ciągu, zwróć go.

->a,b{r=p;(1..l=a.size).map{|i|(0...l).map{|j|b[s=a[j,i]]?0:r||=s}};r}

Burleska - 26 bajtów

W tej chwili najkrótszą drogą, jaką mogę wymyślić, jest:

lnp^sujbcjz[{^p~[n!}f[-][~

Japt , 14 bajtów

Êõ!ãU c k!èV g

Wypróbuj online!

Zwraca, undefinedjeśli nie ma prawidłowego podłańcucha . Różni się to od zwracania ciągu „niezdefiniowany” , chociaż różnica jest widoczna tylko z powodu flagi -Q.

Wyjaśnienie:

Ê                 :Length of the first input
 õ                :For each number in the range [1...length]:
  !ãU             : Get the substrings of the first input with that length
      c           :Flatten to a single array with shorter substrings first
        k         :Remove ones which return non-zero to:
         !èV      : Number of times that substring appears in second input
             g    :Return the shortest remaining substring

Japt -h, 11 bajtów

à f@øX «VøX

Spróbuj

                :Implicit input of strings U & V
à               :All combinations of U
  f@            :Filter each as X
    øX          :  Does U contain X?
       «        :  Logical AND with the negation of
        VøX     :  Does V contain X?
                :Implicit output of last element