Tópicos Extras: Strings e Compressão

Introdução Teórica

O processamento de texto exige algoritmos que fogem do “caractere a caractere” ingênuo (\(O(N \cdot M)\)) para buscas e comparações.

KMP (Knuth-Morris-Pratt)

Para buscar uma palavra \(P\) (tamanho \(M\)) em um texto \(T\) (tamanho \(N\)), o KMP atinge \(O(N+M)\). * Ideia: Se falhamos na comparação no caractere 5 de \(P\), não precisamos voltar ao início. Usamos uma tabela precomputada (tabela \(\pi\) ou LPS - Longest Prefix Suffix) para saber “o quanto podemos pular” aproveitando o que já casou.

Compressão de Huffman

Algoritmo guloso para compressão de dados sem perda. * Caracteres frequentes ganham códigos binários curtos. * Caracteres raros ganham códigos longos. * Cria-se uma árvore binária ótima combinando as frequências menores iterativamente.

Problema Clássico

Problema: Link Bolado (Busca de Padrão) Link: Beecrowd 2651

Descrição: Detectar se a string “zelda” (insensível a maiúsculas) aparece em um texto. Embora simples (função find resolve), aplicar KMP é o treino ideal. Como o texto é grande, \(O(N^2)\) pode ser lento.

Variações e Exercícios

  1. [Cifra de César]
    • Foco: Manipular códigos ASCII. Base para criptografia.
    • Link: Beecrowd 1253
  2. [Alienígenas]
    • Foco: Encontrar padrões repetidos ou contar substrings distintas. Muitas vezes resolvido com Rolling Hash ou Suffix Array.
    • Link: Problemas da OBI (Pesquisar “OBI Alienígenas”). No Beecrowd, problemas de “Distinct Substrings”.
  3. [De Dentro para Fora]
    • Foco: Manipulação de string, inverter metades.
    • Link: Beecrowd 1235
Back to top