Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 - Strings pt2, Rabin–Karp, String Matching Avançado - Coggle Diagram
MM11 - Strings pt2
KMP (Knuth–Morris–Pratt)
- Permite busca eficiente de padrões
- Usa prefix function (lps array) para evitar comparações repetidas
-
Útil para:
- Busca rápida de substrings
- Verificação de padrões repetidos
Rabin–Karp
- Técnica baseada em hashing de strings
-
- Bom para múltiplas buscas ao mesmo tempo
- Complexidade média O(n + m)
- Pode ter colisões → resolve com hash duplo
-
String Matching Avançado
- Algoritmos baseados em automatos
-
Introdução a Trie
- Armazena palavras em forma de árvore
- Útil para autocomplete e dicionários
- Pesquisa rápida por prefixo
-
-