Algoritmo KMP (Knuth-Morris-Pratt) – Esse algoritmo constrói um autômato finito determinístico capaz de reconhecer o padrão buscado e, então, simula a execução desse autômato ao longo do texto de entrada.
Algoritmo Rabin-Karp – Esse algoritmo funciona deslizando uma janela de comparação pelo texto de entrada e usando uma função de hash para decidir quando uma comparação entre o trecho de texto e o padrão buscado deve ser feita.
Algoritmo BMH (Boyer-Moore-Horspool) – Esse algoritmo funciona deslizando uma janela de comparação pelo texto de entrada e usando uma “tabela de saltos” para decidir em quantos símbolos a janela deslizante deve ser deslocada, quando ocorre um descasamento ocorre entre um símbolo na janela deslizante o no padrão buscado.
Métricas em Strings
Algoritmo de Levenshtein – Esse algoritmo calcula a distância de Levenshtein entre duas strings – o número mínimo inserções, exclusões ou substituições necessárias para transformar uma string em outra.
Algoritmo LCS (Longest Common Subsequence) – Esse algoritmo encontra a maior subsequência comum entre duas sequências. Os elementos nesta subsequência não necessariamente devem ser contíguos nas sequências de entradas.