Nesse desafio, sua tarefa é localizar substrings com uma determinada estrutura.
Entrada
Sua entrada deve ser duas cadeias alfanuméricas não vazias, um padrão p
e um texto t
. A ideia é que cada caractere p
represente uma subcadeia não vazia contígua da t
qual ocorra um ao lado do outro e p
represente sua concatenação. Caracteres idênticos correspondem a substrings idênticos; por exemplo, o padrão aa
representa qualquer quadrado não vazio (uma sequência obtida concatenando uma sequência mais curta para si mesma). Assim, o padrão aa
pode corresponder à substring byebye
, a cada a
correspondência bye
.
Resultado
Se o texto t
contiver uma substring que p
corresponda, sua saída será essa substring, com dois pontos :
inseridos entre as strings que correspondem aos caracteres de p
. Por exemplo, se tivermos t = byebyenow
e p = aa
, então bye:bye
é uma saída aceitável. Pode haver várias opções para a substring correspondente, mas você deve gerar apenas uma delas.
Se t
não contiver uma substring correspondente, sua saída será um rosto triste :(
.
Regras e esclarecimentos
Caracteres diferentes de p
podem corresponder a substrings idênticos, portanto, p = aba
podem corresponder à string AAA
. Observe que os caracteres devem corresponder a cadeias não vazias; em particular, se p
for maior que t
, a saída deve ser :(
.
Você pode escrever um programa completo ou uma função e também pode alterar a ordem das duas entradas. A menor contagem de bytes vence e as brechas padrão não são permitidas.
Casos de teste
Dado no formato pattern text -> output
. Observe que outras saídas aceitáveis podem existir.
a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
fonte
O(2^((n * (n + 1))/2))
: PRespostas:
Python, 207 bytes
Ligue com
g(pattern, string)
Usa o
re
módulo para fazer a maior parte do trabalho.fonte
JavaScript (SpiderMonkey) (ES5.1), 198 bytes
Desde que o ES6 foi lançado em junho de 2015, publico a versão ES5.1 do código junto com o equivalente ao ES6, mas declaro a versão ES5.1 como a principal resposta.
Correspondência gananciosa, portanto, o primeiro caso retorna "Não" em vez de "N".
Experimente online!
JavaScript (Node.js) (ES6), 141 bytes
Experimente online!
Adota os argumentos ao currying sintaxe:
f(a)(b)
Explicação (e não destruída):
fonte
Braquilog , 35 bytes
Experimente online!
Em entradas não muito pequenas, muito lentas. Na verdade, eu não fiz o sexto caso de teste, mas não por falta de tentativa. (Provavelmente devido à força bruta de todas as partições de cada substring, começando pela maior e, em seguida, verificando se é uma correspondência.) Recebe a entrada como uma lista
[pattern,string]
.Explicação condensada e dividida:
sᵗ~cᵗX
X é o padrão emparelhado com uma partição de uma substring da sequência de entrada.
lᵛ
O padrão e a partição têm o mesmo número de elementos.
Xzdz≠ʰ
Dois
pattern char, matched substring
pares únicos não compartilham um caractere padrão. Ou seja, nenhum caractere padrão é mapeado para várias substrings, embora vários caracteres padrão possam ser mapeados para uma substring.Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("
A saída são os elementos da partição unida por dois pontos, a menos que algo não possa ser feito; nesse caso, é
:(
.Explicação monolítica:
fonte