Tarefa
A tarefa é jogar golfe em um algoritmo de correspondência exata de seqüência em tempo real de sua escolha.
Entrada
Duas linhas de texto fornecidas na entrada padrão, separadas por uma nova linha. A primeira linha contém o "padrão" e será simplesmente uma string ASCII desenhada a partir das letras a-z
.
A segunda linha contém o "texto" mais longo e também será simplesmente uma string ASCII desenhada a partir das letras a-z
.
Resultado
Uma lista de índices de onde as correspondências exatas ocorrem. Você deve exibir a posição do início de cada partida que ocorrer.
Especificação
Seu algoritmo pode gastar tempo linear pré-processando o padrão. Em seguida, ele deve ler o texto da esquerda para a direita e levar um tempo constante para cada caractere no texto e gerar qualquer nova correspondência assim que ela ocorrer. É claro que as partidas podem se sobrepor.
Algoritmo
Existem muitos algoritmos de correspondência exata em tempo real. Um é mencionado no wiki do KMP, por exemplo. Você pode usar qualquer um que quiser, mas sempre deve dar a resposta certa.
Manterei uma tabela de líderes por idioma para que aqueles que preferem os idiomas populares também possam vencer à sua maneira. Por favor, explique qual algoritmo você implementou.
Tempo real
Parece que houve muita confusão sobre o que significa tempo real. Isso não significa simplesmente tempo linear. Portanto, o KMP padrão não é em tempo real. O link na pergunta aponta explicitamente para uma parte da página wiki do KMP sobre uma variante em tempo real do KMP. Nem Boyer-Moore-Galil é em tempo real. Esta pergunta / resposta da história discute o problema ou é possível pesquisar no Google "correspondência exata em tempo real" ou termos semelhantes.
fonte
abcd
eacbdefg
, eu produziria1 4
, paraa
ed
?a
ed
combinar. Existeabcd
eacbdefg
, e oa
ed
estão em posições idênticas.Respostas:
Python 2, 495 bytes
Este é um KMP em tempo real, muito mais curto e apenas um pouco mais lento que o algoritmo BMG (que geralmente é sublinear). Ligue com
K(pattern, text)
; saída é idêntica ao algoritmo BMG.fonte
Python 2, 937 bytes
Isso não é curto, de forma alguma, mas (a) funciona, (b) atende a todos os requisitos e (c) é praticado tanto quanto eu puder.
Esta é uma implementação do algoritmo Boyer-Moore-Galil. Bem simples - ligue com
S(pattern,text)
; as outras duas funções são usadas no pré-processamento. De fato, tudo, exceto as últimas 5 linhas, é pré-processamento.Um exemplo de execução, que levou cerca de um segundo:
fonte
O(m)
pré-processamento e naO(n)
correspondência [=>O(n+m)
], o que faz (ou melhor).O(n+m)
demorar, mas leva um tempo para um dos símbolos no texto, por exemplo.KMP, Python 2 (213 bytes)
Versão não destruída. O primeiro loop é criar os autômatos do KMP. O segundo loop está andando nos autômatos. Eles compartilham quase o mesmo padrão, mas abstraí-los custará mais bytes; portanto, para um código de golfe, eu prefiro duplicar essa lógica. Implementação semelhante é realmente amplamente usada em concursos de programação.
fonte
KMP em tempo real, Python 2 (167 bytes)
No KMP normal, simulamos o comportamento do autômato usando uma função de falha. Nesse KMP em tempo real, o autômato completo é construído para que na frase correspondente ele possa processar cada caractere em tempo real (tempo constante).
A complexidade do tempo e do espaço de pré-processamento é O (nm), onde m é o tamanho do alfabeto en é o comprimento da sequência de padrões. No entanto, em meus testes, o tamanho real da tabela de transição é sempre menor que 2n, portanto, talvez possamos provar que a complexidade do tempo e do espaço é O (n).
Versão ungolfed
fonte
Q, 146 bytes
Teste
gera 15 e 34
Notas
Não restrito ao alfabeto (suporta qualquer caractere ascii e diferencia maiúsculas de minúsculas).
Não usa nenhuma das operações específicas definidas por Q sobre seqüências de caracteres -> funciona em seqüências de caracteres (sequências (operações, correspondência, comprimento etc.)
Minimiza a tabela de transição que une todos os caracteres que não estão no padrão como uma única classe de caracteres.
Eu posso apertar um pouco o código. É uma primeira tentativa de validar a estratégia da solução
Visite qualquer caractere de texto exatamente uma vez e, para cada caractere de entrada, há um salto exclusivo. Então, suponho que a pesquisa se encaixe como 'tempo real'
O estado da construção da tabela i e char c procura a substring mais longa que termina em ie após o acréscimo de c é um prefixo de S. A construção não é otimizada, portanto, não sei se é válido
O formato de entrada não se encaixa bem com o idioma. Passar dois argumentos de string economizará 16 bytes
Explicação
W global representa padrão e S corresponde ao texto a ser pesquisado
x:1_"\n "\:x
código estranho para lidar com os requisitos de entrada (Q requer que essas cadeias de linhas múltiplas não tenham a primeira linha recuada, portanto, ele deve descartar espaço adicional na frente de todas as linhas que não são a primeira)n::#W
calcula o comprimento W e salva como n globalu::?W
calcula caracteres únicos em W e salva como u globalu?S
gera a classe de caracteres para cada caractere de SConstrua uma tabela de transição T com uma linha por caractere exclusivo em W (mais um extra) e uma coluna para cada índice em W (mais um extra). A linha extra corresponde ao estado inicial e a coluna extra coleta qualquer caractere em S, mas não em W. Essa estratégia minimiza o tamanho da tabela
p:{$[n<#x;0;x~(#x)#W;#x;0]}
é a função que procura o prefixo mais longof:{{|/p'x}'((1_)\x#W),\:/:u}
é a função que calcula uma linha x de TPesquise texto usando a tabela de transição.
T\[0;u?S]
itera mais de 0 (estado inicial) e cada classe de caractere de S, usando como novo valor o valor na tabela de transição T [state] [charClass]. Os estados finais têm o valor n, portanto, procuramos esse valor na sequência de estados e o retornamos ajustado (para indicar a posição inicial em vez da posição final de cada partida)fonte
Boyer-Moore, Perl (50)
Perl tenta usar Boyer-Moore naturalmente:
fonte