Dada uma sequência como argumento, produza o comprimento da (s) mais longa (s) substring (s) repetida (s) sobreposta (s) ou zero se não houver essa sequência.
Você pode assumir que a sequência de entrada não está vazia.
Exemplos
abcdefabc
: a substring abc
é repetida nas posições 1 e 7, portanto, o programa deve gerar 3
abcabcabcabcab
: abcabc
ou bcabca
ou cabcab
são repetidos, portanto, o programa deve gerar 6 . (a substring abcabcabcab
também é repetida, mas as ocorrências se sobrepõem, então não a aceitamos).
aaaaaaa
: aaa
é repetido nas posições 1 e 4, por exemplo, portanto, o programa deve gerar 3
abcda
: a
é repetido, então o programa deve gerar 1
xyz
: sem sequência repetida → 0
ababcabcabcabcab
: deve retornar 6
Isso é código-golfe , e o menor número de bytes vence.
fonte
Respostas:
brainfuck, 226 bytes
Formatado:
Espera a entrada com ou sem uma nova linha à direita e gera o resultado como um valor de byte .
Experimente online.
Isso verifica cada prefixo para ver se ocorre mais tarde na sequência, corta o primeiro caractere e repete o processo até que não haja mais caracteres.
A fita é dividida em nós de três células,
c 0 f
onde
c
é um caractere da sequência especificada ef
é um sinalizador que pode ser um, negativo ou zero. Sinalizadores diferentes de zero são colocados entre os dois caracteres atualmente sendo comparados e negativos são reservados para as células após o final do prefixo atual e antes do início do sufixo atual (ou seja, antes do índice da correspondência potencial atual).O resultado é armazenado à esquerda da string e é atualizado sempre que uma correspondência é encontrada.
(A cadeia é realmente processada ao contrário com um
\x01
anexo a ela.)fonte
Gelatina , 12 bytes
Experimente online!
Como funciona
fonte
œ-Q
é realmente legal.Perl 6 , 36 bytes
Tente
Expandido:
fonte
Retina ,
353230 bytesDesafio bem legal.
Experimente online
Explicação:
fonte
M%`.
como o segundo estágio.JavaScript (ES6),
796866 bytesEditar: salvou
1113 bytes graças a @Arnauld.fonte
Haskell , 79 bytes
Experimente online!
fonte
%
pode acumular uma subsequência não contíguas, dando falsos positivos como 2 paraaa
emaxayaa
,a%d
está errada, mas também desnecessária. O que também significa que você pode usar emmax
vez demaximum
.a%d
para""%d
consertar isso.a
está vazio.sum[1|(x,y)<-zip a c,x==y]
pode ser usado em vez dea!c
.Python 3 ,
7572 bytesExperimente online!
fonte
JavaScript, 120
fonte
Casca , 11 bytes
Experimente online!
Nota: Husk é mais recente que esse desafio.
Explicação
fonte
Perl 5 com
-p
, 40 bytesExperimente online!
fonte
Mathematica,
7565 bytes10 bytes salvos devido a @JingHwan Min .
Função anônima. Pega uma string como entrada e retorna um número como saída.
fonte
BlankNullSequence (___)
quandoOverlaps->All
estiver lá.Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&
ficaria bem.StringReplace
: PPitão - 16 bytes
Preciso jogar golfe convertendo todas as cordas em comprimentos e encontrando o máximo.
Conjunto de Teste .
fonte
Clojure, 112 bytes
faz um loop duas vezes sobre os números
0
emn - 1
(n
sendo o comprimento da string), solta osj
caracteres e divide o restante em partes "inicial" e "final". Cria um conjunto de todas as substringse
de comprimentob
e o utiliza como uma função para verificar seb
é encontrado a partir daí. Retorna o comprimento deb
se encontrado e 0, caso contrário, retorna o máximo desses valores.Seria interessante ver uma versão mais curta.
fonte
Retina , 24 bytes
Experimente online!
Um aquecimento para eu aprender os novos recursos do Retina 1.
Explicação
Um estágio List, retorna todas as correspondências para a regex
(.*).*\1
, que corresponde a qualquer padrão no formato "ABA", onde A e B são duas substrings arbitrárias (possivelmente vazias). As opções adicionais fornecidas para este estágio sãov
, que considera correspondências sobrepostas e$
que aplica uma substituição a cada uma das correspondências antes de devolvê-la: a substituição é indicada na segunda linha e corresponde ao comprimento (.
) do primeiro grupo de captura ( qual seria a subcadeia "A" no exemplo anterior).Agora temos todos os comprimentos de substrings repetidos, esse estágio simplesmente os classifica em ordem numérica, do mais curto ao mais longo.
Por fim, esse estágio grep (
G
) mantém apenas o último-1
resultado ( ), que é o comprimento da substring repetida mais longa.fonte
Javascript, 165 bytes
Casos de teste
fonte
ababcabcabcabcab
, mas a sequênciacabcab
é repetida.