Dadas (em STDIN, como argumentos de linha de comando ou argumentos de função) duas seqüências de caracteres não vazias distintas, localize e retorne a menor substring da primeira string que não é uma substring da segunda. Se não existir essa substring, você pode retornar a string vazia, retornar qualquer string que não seja uma substring da string original ou lançar uma exceção. Se você estiver retornando de uma função, também poderá retornar nulo (ou indefinido, Nenhum etc.) nesse caso. Se várias dessas substrings estiverem vinculadas pelo menor tempo, você poderá retornar qualquer uma delas.

As strings podem consistir em qualquer caractere ASCII imprimível.

As entradas fornecidas no STDIN serão fornecidas com uma string em cada linha. A seu pedido, uma única linha vazia pode ser adicionada no final da entrada.

Isso é código de golfe, então o programa válido mais curto vence.

ALGUNS CASOS DE TESTE

ENTRADA:

STRING ONE
STRING TWO

RESULTADO:

E

ENTRADA:

A&&C
A&$C

SAÍDAS VÁLIDAS:

&&
&C

ENTRADA:

(Duas seqüências de 80 letras geradas aleatoriamente)

QIJYXPYWIWESWBRFWUHEERVQFJROYIXNKPKVDDFFZBUNBRZVUEYKLURBJCZJYMINCZNQEYKRADRYSWMH
HAXUDFLYFSLABUCXUWNHPSGQUXMQUIQYRWVIXGNKJGYUTWMLLPRIZDRLFXWKXOBOOEFESKNCUIFHNLFE

TODAS AS SAÍDAS VÁLIDAS:

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

Braquilog , 23 bytes

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

Funciona no transpiler Java antigo. Espera as duas seqüências em uma lista como entrada, unifica a saída com a substring. Se nenhuma substring for encontrada, retornará false.

Infelizmente ainda não codifiquei o subconjunto embutido no novo transpilador Prolog.

Explicação

: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]

Casos de teste:

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

Trabalhando em torná-lo mais curto, mas este é o meu instinto cerebral. Ainda não é realmente um jogador de golfe.

Obrigado a @ user81655 e @NonlinearFruit pelos bytes extras.

Editar :

Dang. Tentei este código:

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

Pensei que fosse alguns bytes mais curto. Acontece que era 1 byte a mais do que eu tinha antes da edição.

Python, 87 86 bytes

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]

Se existir, retornará o mais à esquerda de todas as substrings únicas mais curtas.

Se não houver substring exclusivo, um IndexError será gerado.

Teste em Ideone .

Python, 82 bytes

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

Uso: f('A&&C', 'A&$C') -> retornos'&&'

Gera ValueError se não houver substring adequado.

Explicação:

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''}cria recursivamente um conjunto de substrings de u f=lambda s,t:min(g(s)-g(t),key=len)leva o menor substring da diferença de conjunto

JavaScript (ES6), 79 bytes

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>

Se o retorno falsefor aceitável, salve 2 bytes usando em &&svez de ?s:''.

Pitão, 11 bytes

Jwhf!}TJ.:z

Experimente online!

JavaScript (Firefox), 80 bytes

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

O teste funciona apenas no Firefox. Retorna undefinedse não houver substring.

Retina , 37 bytes

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

A saída estará vazia se nenhuma substring válida for encontrada A.

Experimente online! (Levemente modificado para executar vários casos de teste ao mesmo tempo. O formato de entrada é na verdade separado por avanço de linha, mas os conjuntos de testes são mais fáceis de escrever com um caso de teste por linha. A estrutura de teste transforma o espaço em um avanço de linha antes do início do código real.)

Explicação

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

Para cada posição inicial possível em A, corresponda à substring mais curta que não aparece B. O &é para correspondências sobrepostas, de modo que tentamos todas as posições iniciais, mesmo que uma correspondência tenha mais de um caractere. Os \Ggarante que não pular nenhuma posições - em particular, desta forma, temos de parada no avanço de linha, de modo que nós não temos partidas adicionais a partir , por isso, vai todos os substrings que começam mais para a direita da posição atual, de modo descartando isso não é um problema (e realmente melhora o desempenho).B si. A razão pela qual isso não atrapalha as coisas é realmente bastante sutil: porque se houver uma posição inicial em Aque não possamos encontrar nenhuma substring válida, também será uma falha que fará com \Gque pare de verificar outras posições. No entanto, se (a partir da posição inicial atual) todas as substrings apareceremB

Devido à M!configuração, todas essas correspondências serão retornadas do estágio, unidas aos feeds de linha.

O$#`.+
$.&

Isso classifica as linhas do resultado anterior por comprimento. Isso é feito combinando a linha com .+. Em seguida, $ativa uma forma de "ordenar por", de modo que a correspondência seja substituída por $.&para determinar a ordem de classificação. O $.&próprio substitui a partida pelo seu comprimento. Finalmente, a #opção informa ao Retina para classificar numericamente (caso contrário, trataria os números resultantes como seqüências de caracteres e os classificaria lexicograficamente).

G1`

Finalmente, mantemos apenas a primeira linha, usando um estágio grep com um regex vazio (que sempre corresponde) e um limite de 1.

Perl, 87 85

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

Essa é uma função anônima que retorna o primeiro (por posição) dos substrings mais curtos $_[0]que não ocorrem $_[1]ou undefse não existe nenhum substring.

Programa de teste com seqüências de caracteres retiradas da resposta de @ iAmMortos, testadas com Perl 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 bytes

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

Exemplo de uso: "abcd" # "dabc"-> "cd".

Uma implementação direta: construa todas as subseqüências ae mantenha as que não aparecem b. argminretorna um elemento de uma lista que minimiza a função dada a 2ª argumento, aqui: length.

Pitão - 9 6 bytes

h-Fm.:

Experimente online aqui .

C #, 152 bytes

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

Ruby, 70 bytes

Coleta todas as substrings de um determinado comprimento da primeira string e, se houver uma que não esteja na segunda, retorne-a.

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

Burlesco - 26 bytes

No momento, a maneira mais rápida de obter é:

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

Japonês , 14 bytes

Êõ!ãU c k!èV g

Experimente online!

Retorna undefinedse não houver substring válido . Isso é diferente de retornar a sequência "indefinida" , embora a diferença seja visível apenas devido ao sinalizador -Q.

Explicação:

Ê                 :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

Japonês -h, 11 bytes

à f@øX «VøX

Tente

                :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