Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 6: String Processing - Coggle Diagram
Capítulo 6: String Processing
6.1 Overview and Motivation
String Processing é comum em ICPC e bioinformática (DNA = strings longas)
Necessidade: algoritmos rápidos e estruturas eficientes
ICPC: maioria dos problemas envolve strings curtas
IOI: problemas de parsing e output formatting
6.2 Basic String Processing Skills
Competências essenciais:
Leitura de strings
Parsing de tokens
Concatenação
Contagem de caracteres
Busca de substring simples
Exercícios fundamentais para ICPC
Tarefas exemplificadas:
(1) Entrada multi-linha até condição de parada
Manipulação básica de string
(2) Procurar substring em T
Encontrar todas as ocorrências
Casos especiais (maiúsculas/minúsculas)
(3) Operações simples:
Contar dígitos, vogais, consoantes
O(n)
(4) Tokenização:
Dividir frase em palavras
Ordenar tokens lexicograficamente
(5) Contar frequência de palavras
Usar hash map
(6) Saber número de caracteres da última linha
Conclusão: habilidades fundamentais antes de algoritmos avançados
6.3 Ad Hoc String Processing Problems
Problemas que exigem apenas manipulação simples de strings
Subcategorias:
Cipher / Encode / Decode
Criptografia simples
XOR, soma ASCII, shifts, etc.
Muitos problemas UVa
Frequency Counting
Contar letras, palavras, símbolos
Uso de tabela direta ou hash
Input Parsing
Processar texto complexo
Importante em ICPC
Regex com Java String/Pattern
Casos em que regex simplifica muito
Exemplo: identificar números reais
Output Formatting
Alinhar texto, formatar colunas
Usado como "time wasters" em ICPC
String Comparison
Comparar strings por critérios diversos
Just Ad Hoc
Qualquer outra manipulação específica
6.4 String Matching
Definição: encontrar índice de P dentro de T
Exemplos:
T = "STEVEN EVENT"
P = "EVE" ou "EVENT"
6.4.1 Library Solutions
C: strstr
C++: find
Java: indexOf
Úteis para strings curtas
6.4.2 Knuth-Morris-Pratt (KMP)
Motivação:
Naive matching é O(nm) pior caso
Textos repetitivos = TLE
Ideia:
Usar prefixo que é também sufixo (border)
Evitar recomparação
Componentes:
Pré-processamento do padrão → tabela b[]
Busca linear O(n)
Algoritmo:
b[i]: tamanho do maior prefixo = sufixo até i
Em mismatch:
voltar j = b[j]
Em match:
avançar i e j
Complexidade: O(n + m)
Observações:
Evita retrocessos desnecessários
Excelente para padrões com repetições ("AAAAAB")
6.4.3 String Matching in a 2D Grid
Matching em matriz n×m
Percorrer 8 direções (ou menos)
Resolver via backtracking
Otimização: pruning (depth-limited search)
Usado em problemas UVa (ex.: Where’s Waldorf?)
6.5 String Processing with Dynamic Programming
Introdução:
DP resolve problemas de comparação/edição de strings
Trabalha com caracteres (não substrings)
Principais problemas:
6.5.1 String Alignment (Edit Distance)
Objetivo:
Encontrar alinhamento ótimo entre A e B
Minimizar custo de operações
Operações:
match: +2
mismatch (replace): –1
insert: –1
delete: –1
Matriz DP:
V(i, j): melhor alinhamento entre A[1..i] e B[1..j]
Base cases:
V(0, j) = j * score(delete)
V(i, 0) = i * score(delete)
Transição:
option1 = V(i-1, j-1) + score(A[i], B[j])
option2 = V(i-1, j) + score(delete)
option3 = V(i, j-1) + score(insert)
V(i, j) = max(option1, option2, option3)
Complexidade: O(nm)
Alinhamento recuperado percorrendo DP de trás pra frente
Relação com Needleman–Wunsch
6.5.2 Longest Common Subsequence (LCS)
Definição:
Maior subsequência comum (não precisa ser contínua)
Exemplos:
A = “ACACTC”
B = “AGCATGC”
LCS = “ACATC” (tamanho 5)
DP:
Se A[i] == B[j]:
L[i][j] = L[i-1][j-1] + 1
Senão:
L[i][j] = max(L[i-1][j], L[i][j-1])
Complexidade: O(nm)
Aplicações:
Hamming distance (para strings de mesmo tamanho)
Permutações (LIS-like)
6.5.3 Non Classical String Processing with DP
Definição:
len(l,r): maior palíndromo em S[l..r]
Base:
l == r → 1
l > r → 0
Recorrências:
Se S[l] == S[r]:
len(l,r) = 2 + len(l+1, r-1)
Caso contrário:
len(l,r) = max(len(l+1,r), len(l,r-1))
Complexidade: O(n²)
Extensão: palíndromo sem deletar → caso especial