Quão compatíveis são minhas cordas?

12

Introdução

Considere duas seqüências A e B do mesmo comprimento L e um número inteiro K ≥ 0 . Para os propósitos deste desafio, dizemos que as cadeias são compatíveis com K , se existir uma cadeia C de comprimento K, de modo que A seja uma substring contígua da concatenação BCB . Observe que A é uma substring do BAB , portanto A e B são sempre compatíveis com L (mas também podem ser compatíveis com K para alguns outros K <L ).

Entrada

Suas entradas são duas cadeias do mesmo comprimento positivo, consistindo em letras ASCII maiúsculas e minúsculas.

Resultado

Sua saída deve ser o menor inteiro não negativo K, de modo que as entradas sejam compatíveis com K.

Exemplo

Considere as entradas

A = HHHHHH
B = HHttHH

Eles não são compatíveis com 0, porque A não é uma substring de HHttHHHHttHH. Eles também não são compatíveis com 1, porque A não é uma substring, HHttHH#HHttHHnão importa qual letra seja colocada no #. No entanto, A é uma substring de HHttHHHHHHttHH, onde C é a cadeia de duas letras HH. Assim, as entradas são compatíveis com 2 e a saída correta é 2.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Casos de teste

A condição de compatibilidade é simétrica, portanto, a troca das duas entradas não deve alterar a saída.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

Entre os melhores

Aqui está um snippet de pilha para gerar um placar e uma lista de vencedores por idioma. Para garantir que sua resposta seja exibida, inicie-a com um cabeçalho do formulário

## Language, N bytes

Você pode manter pontuações antigas no cabeçalho usando as tags tachado: <s>57</s>aparecerá como 57 .

Mostrar snippet de código

code-golf string Zgarb
fonte

Respostas:

8

Pyth, 16

lhf}QjT,vzvz+k.:

Encontre a substring mais curta de A que, quando inserida entre duas cópias de B, resulta em uma sequência que contém A.

Isso pode ser dois bytes mais curto se a segunda linha não tiver aspas, mas isso parece estranho?

Suíte de teste

FryAmTheEggman
fonte
4

Python 3, 155 168 157 bytes

Total é o comprimento de A. Compare o início do Afinal Be subtraia-o do total. Compare o início do Bfinal Ae subtraia-o do total. Retorne o valor absoluto do total, a menos que total seja igual ao comprimento; nesse caso, retorne 0.

def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

Editar: lidar com o f("abcdab","cdabcd")==2caso

NonlinearFruit
fonte
3
Infelizmente, isso não funciona para f("abcdab", "cdabcd")o que deve ser 2.
Neil
@ Neil Boa captura. Vou adicionar isso aos casos de teste.
Zgarb
1
Isso foi inesperado. ( Global Twitch Emotes )
F. George
@ mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu Eu estava olhando a imagem e pensando: 'Esta é uma idéia bacana do depurador para usar emojis, mas não vejo um bug ...'. Eu acho que esse complemento causaria estragos neste site.
NonlinearFruit
3

Retina , 49 bytes

.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+
$#4

Experimente online! (Ligeiramente modificado para executar todos os testes de uma vez.)

O truque é que precisamos voltar atrás na parte em Aque não encontramos B, e até agora não encontrei uma maneira de fazer isso sem olhar para o lado irritante e equilibrar os grupos.

Martin Ender
fonte
3

Jolf, 40 bytes

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

Tente!

Eu sou muito novo em Jolf, aprendi muito ao descobrir isso. Parece um pouco estranho, ainda provavelmente poderia ser jogado para baixo ainda mais. Mesmo derrubou 2 bytes enquanto escrevia esta explicação.

Explicação:

  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print
incha
fonte
Eu não tentei a sério, e isso pode ser uma solução ideal, mas sugiro tentar mapear sobre intervalos. ( s0zliLhe dará uma array [0 ... comprimento i] se quiser tentar essa abordagem.)
Conor O'Brien
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, vou dar uma olhada ... também existe um comando if que eu rejeitei enquanto procurava na documentação / fonte ou é a única opção? com um terceiro argumento irrelevante?
swells
?é o mais próximo de um se houver em Jolf. É como um ternário se. ?ABCs returns B` se a for verdadeiro e Ccaso contrário.
Conor O'Brien
2

JavaScript (ES6), 110 bytes

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

Funciona cortando pedaços cada vez mais longos do meio aaté que coincidam com as duas extremidades b. O loop não é infinito, pois irá parar no ou antes i == a.length.

Neil
fonte