Lançado · em melhoria
Algorithm
Algoritmos de strings encontram padrões em textos e palavras por prefixo; KMP, Rabin-Karp, tries e o algoritmo Z são as técnicas centrais.
Algoritmos de strings são métodos para comparar e buscar sequências de caracteres de forma rápida e correta. O problema central é a busca de padrões: encontrar todas as posições em que um padrão curto aparece em um texto longo. Também fazem parte da área buscar todas as palavras de um dicionário que começam com um prefixo e localizar muitos padrões de uma só vez. A abordagem ingênua, que testa cada posição, pode levar um tempo proporcional ao produto do tamanho do texto pelo tamanho do padrão.
A busca em editores, a busca em logs, o preenchimento automático, a detecção de intrusão, a sincronização de arquivos e a análise de genomas dependem de algoritmos de strings. O KMP reaproveita as comparações já feitas por meio de uma tabela de falhas e garante tempo linear, o Rabin-Karp desliza um hash rolante pelo texto para evitar a maioria das comparações, e uma trie compartilha prefixos comuns, de modo que a busca por prefixo depende só do tamanho da palavra. O tema também aparece com frequência em entrevistas técnicas.
Comece pelo vocabulário de prefixos, sufixos e bordas e confira à mão por que a busca ingênua é lenta. Depois, calcule você mesmo a função de prefixo de um padrão pequeno, implemente a busca KMP e uma trie e compare os resultados com a biblioteca padrão. Por fim, veja as armadilhas que deixam os resultados errados na prática, como colisões de hash e normalização Unicode.
Calcula-se antes a maior borda de cada prefixo do padrão; quando há divergência, a busca passa para uma borda menor sem voltar no texto, com custo O(n + m).
O Rabin-Karp atualiza em O(1) o hash de cada janela de tamanho m, compara com o hash do padrão e só confere os caracteres quando os hashes são iguais.
Uma árvore percorrida caractere a caractere; prefixos comuns são guardados uma única vez, então a busca por prefixo e o preenchimento automático dependem só do tamanho da palavra.
O vetor Z fornece, para cada posição e em tempo linear, o maior prefixo comum com a string inteira. Em textos reais, também é preciso cuidar da normalização e das unidades de índice.
prefix_function calcula a maior borda de cada prefixo do padrão, e kmp_search usa essa tabela para ler o texto uma única vez, da esquerda para a direita, reunindo todas as posições iniciais. Como k volta para pi[k - 1] após cada ocorrência, ocorrências sobrepostas, como as de 0 e 2, também são encontradas. Execute python string_search.py para imprimir os dois resultados.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.pySeis capítulos que levam você da instalação aos conceitos essenciais de Algoritmos de strings.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Algoritmos de strings.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.