Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM10 - Processamento de Strings - Coggle Diagram
MM10 - Processamento de Strings
Visão geral e motivação
Importância
Uso em ICPC (concursos) e bioinformática (strings longas: DNA, etc.)
Diferença entre ICPC e IOI: IOI tem restrições de enunciados/IO; ICPC exige parser/formatos variados
Estrutura do capítulo
6.1 Overview e Motivation
6.2 Habilidades básicas de processamento de strings
6.3 Problemas Ad Hoc
6.4 String Matching (busca de padrões)
6.5 Processamento com Programação Dinâmica (DP)
6.6 Estruturas de dados eficientes (Suffix Trie/Tree/Array)
Aplicações práticas
Busca de padrões, compressão, bioinformática, indexação, validação de formatos
6.2 Habilidades básicas (práticas e teoria)
Operações fundamentais
Armazenamento de strings
Em C: arrays de char + terminador '\0'
Em C++: std::string (gestão automática de tamanho)
Em Java: String (imutável) e StringBuilder/StringBuffer (mutável, concatenar)
Leitura linha a linha
C: fgets / getline
C++: std::getline(cin, s)
Java: BufferedReader.readLine()
Concatenação eficiente
Evitar concatenação repetida em laços com strings imutáveis (use StringBuilder / reservar capacidade)
Verificação de prefixo (linha começa com ".......")
Comparar primeiro k caracteres ou usar startsWith / compare de memcmp
Busca de substring (teoria e prática)
Problema: encontrar todas as ocorrências de P em T
Soluções:
Funções de biblioteca (strstr, find, indexOf) — convenientes, suficientes para textos curtos
Algoritmos especializados: KMP, Z-algoritmo, Boyer–Moore, Rabin–Karp
Complexidade:
Busca ingênua: pior caso O(nm), típico O(n)
KMP: O(n + m) (pré-processamento do padrão + busca)
Rabin–Karp (hash rolling): O(n + m) esperado, depende de colisões
Análise de caracteres e normalização
Contagens em O(n): dígitos, vogais, consoantes
Transformação para minúsculas / remoção de acentuação (normalização Unicode)
Tokenização e manipulação de palavras
Delimitadores: espaços, pontos, outros símbolos
Métodos: split por regex, parser manual para maior controle
Armazenamento: vetor/ArrayList/deque de tokens
Ordenação lexicográfica: O(k log k * L) onde k = número de tokens, L = custo comparação média
Frequência de palavras
Estruturas:
Hash map (C++ unordered_map / Java HashMap) — média O(1) por operação
Tree map (C++ map / Java TreeMap) — O(log n) por operação, útil se precisar de ordenação
Contagem e seleção do mais frequente (scan único após agrupar)
Leitura de linha de tamanho desconhecido
Usar funções streaming que crescem dinamicamente (getline em C, std::string recebe qualquer tamanho em C++)
Em C, alocar buffer dinâmico e realocar conforme necessidade
6.3 Problemas Ad Hoc (categorias e teoria)
Cifras / Codificação / Criptografia simples
Substituição, César, Vigenère, cifra por transposição
Padrões: mapear caracteres, tratar casos e limites
Testes: alfabetos, dígitos, preservação de espaços/pontuação
Contagem de frequência
Letras vs. palavras: direct addressing para letras, hash map para palavras
Normalização: case-folding, remoção de pontuação
Parsing de entrada (input parsing)
Parsing iterativo (state machine simples) vs. parser recursivo (gramáticas complexas)
Técnicas: tokenização, análise léxica, análise sintática (rec. descendente)
Expressões regulares (Regex)
Poder: correspondência, substituições, extração
Usos rápidos: validação (ex.: números reais), contar palavras, limpar texto
Limitações: cuidado com backtracking exponencial em regex mal projetada
Formatação de saída
Controlar padding, alinhamento, quebras de linha, número de casas decimais
Comparação de strings
Igualdade exata, comparação lexicográfica, comparação "fuzzy" (edit distance)
Dicas práticas
Testar casos extremos e entradas com caracteres repetidos
Preferir bibliotecas quando corretas e suficientemente rápidas; implementar algoritmo próprio se houver restrições de pior caso
6.4 String Matching (detalhes teóricos)
Problema formal
Dados T[0..n-1] e P[0..m-1], encontrar todos i tal que T[i..i+m-1] = P[0..m-1]
Soluções e complexidades
Busca ingênua: O(nm) pior caso
KMP (Knuth–Morris–Pratt)
Intuição: reutilizar pré-comparações do padrão (borders / prefix function)
Pré-processamento: construir tabela pi/b (também chamada de failure function) em O(m)
Busca: O(n) — nunca reexamina caracteres de T que já foram casados
Exemplo de uso e casos de teste adversos (padrões repetitivos)
Z-algoritmo
Computa o array Z para a concatenação P + '$' + T para encontrar ocorrências
Complexidade O(n + m)
Boyer–Moore / Boyer–Moore–Horspool
Pula mais caracteres usando heurísticas (bad-character, good-suffix)
Bom desempenho em textos naturais; complexidade sublinear em média
Rabin–Karp
Uso de hash rolante para comparação rápida de janelas; bom para múltiplos padrões
Sensível a colisões (usar hash bem escolhido ou dupla verificação)
Implementação prática
Quando usar biblioteca: strings curtas ou quando pior caso não for problema
Quando implementar KMP: entradas maliciosas, necessidade de garantias de tempo
Busca em grelha 2D
Problema: encontrar uma palavra em uma matriz de caracteres
Abordagens:
Backtracking (DFS) com limite de profundidade e marcação de visitados (quando a palavra pode "dobrar")
Para busca em linha reta: varrer cada posição e aplicar matching em 8 direções
Complexidade depende de tamanho do grid R×C, comprimento do padrão m, e conectividade
6.5 Processamento de strings com Programação Dinâmica (teoria e técnica)
Princípios gerais
Modelar subproblemas por índices (i, j) representando prefixos; evitar passar substrings (cópias)
Usar memoização ou tabulação (bottom-up)
6.5.1 String Alignment / Edit Distance (Needleman–Wunsch)
Objetivo: minimizar número de operações (insert/delete/replace) ou maximizar score de alinhamento
Definição V(i, j): melhor pontuação/alinhamento entre A[1..i] e B[1..j]
Recorrência:
V(0,0)=0; V(i,0)=i
cost(delete); V(0,j)=j
cost(insert)
V(i,j) = max{ V(i-1,j-1)+score(A[i],B[j]), V(i-1,j)+score(A[i],
), V(i,j-1)+score(
,B[j]) }
Exemplo de pontuação comum: match +2, mismatch -1, gap -1
Complexidade: tempo O(nm), espaço O(nm) (otimizações: apenas duas linhas para calcular valor; traceback requer armazenar decisões)
Reconstrução (traceback): seguir escolhas a partir de V(n,m)
Aplicações: comparação de sequências biológicas, correção ortográfica
6.5.2 Longest Common Subsequence (LCS)
Problema: maior subsequência comum entre A e B (não necessariamente contígua)
DP clássico:
LCS(i,j) = if A[i]==B[j] then 1+LCS(i-1,j-1) else max(LCS(i-1,j), LCS(i,j-1))
Complexidade: O(nm) tempo e espaço (idem otimizações com Hirschberg para espaço O(min(n,m)))
Relação com Edit Distance: podem reduzir um ao outro com escolhas de custo
Dicas
Para strings longas, usar otimizações de espaço e/ou algoritmos específicos (Hirschberg para LCS)
Evitar construir substrings em recursões — trabalhar com índices
6.6 Estruturas avançadas para strings (teoria resumida)
Suffix Trie
Trie que indexa todos os sufixos de T; construção O(n^2) em memória no pior caso
Pesquisa de padrão em O(m) (m = tamanho do padrão)
Suffix Tree (Ukkonen)
Versão compacta da suffix trie; construção online em O(n)
Suporta buscas, LCP, número de ocorrências, problemas de substring mais complexos em tempo linear
Estrutura complexa de implementar corretamente — usar bibliotecas se disponível
Suffix Array + LCP
Vetor de sufixos ordenados + array LCP (longest common prefix)
Construção: algoritmos O(n log n) ou O(n) (SA-IS)
Menos memória que suffix tree, muito usado em prática para textos grandes
Aplicações
Indexação de texto, buscas rápidas de padrões múltiplos, compressão, problemas de bioinformática
Complexidade e trade-offs
Suffix tree: ótimo tempo, alto custo de código e memória
Suffix array: equilíbrio entre tempo e memória; boa escolha prática
Boas práticas e sugestões de estudo (teoria + prática)
Testar casos adversos (padrões repetitivos, casos limites)
Saber quando usar bibliotecas vs. implementar soluções com garantias de pior caso
Medir complexidade: tempo, espaço, constantes
Praticar com problemas reais (UVa, SPOJ, Kattis)
Leitura recomendada:
Artigos e livros sobre KMP, Ukkonen (suffix tree), SA-IS (suffix array linear), Needleman–Wunsch
Exercícios sugeridos (com notas teóricas)
UVa 10010 — busca 2D (backtracking + pruning)
UVa 325 — validação via regex (entender regex e limites)
Implementar KMP e provar complexidade O(n+m)
Implementar LCS e aplicar otimizações de espaço
Notas rápidas sobre implementação segura
Normalização de input: encodings (UTF-8), remoção de CRLF, trimming
Cuidado com índices (0-based vs 1-based)
Tratamento de maiúsculas/minúsculas e locales
Evitar overflow em DP com custos grandes (usar long quando necessário)