Hashing Polinomial de Strings
Compare substrings em tempo constante.
Hashing Polinomial de Strings é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Comparando subcadeias rapidamente
É comum precisar verificar se duas subcadeias são iguais. Comparações caractere a caractere são lentas, então transformamos cada cadeia em um número. 🔢
A ideia da dispersão
Uma função de dispersão mapeia uma cadeia para um único número inteiro. Se duas cadeias forem diferentes, seus valores de dispersão quase sempre também serão diferentes.
Trate as cadeias como polinômios
Leia cada caractere como um dígito na base p. Essa visão polinomial transforma a cadeia em uma grande soma ponderada.
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pEscolha uma base e um módulo
Escolha uma base prima, como 31, e um módulo primo grande. O módulo mantém os números pequenos e evita estouros.
BASE = 31
MOD = 10**9 + 9Calculando um valor de dispersão
Percorra a cadeia e incorpore cada caractere usando a regra de Horner, aplicando o módulo a cada etapa.
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODValores de dispersão dos prefixos
Armazene um valor de dispersão do prefixo para cada posição. Então, o valor de dispersão de qualquer subcadeia pode ser obtido com uma subtração rápida.
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODPotências da base
Você também deve pré-calcular as potências da base. Elas alinham os dois prefixos quando você faz a subtração.
pw[i] = (pw[i - 1] * BASE) % MODValor de dispersão de subcadeia em O(1)
O valor de dispersão de s[l..r] é uma subtração de dois valores de dispersão de prefixos, escalada por uma potência. Tempo constante por consulta.
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODCuidado com colisões
Duas cadeias diferentes podem ter o mesmo valor de dispersão; isso é uma colisão. É raro, mas às vezes as competições criam entradas para provocá-la.
Dupla dispersão para segurança
Use dois módulos independentes e compare os dois valores de dispersão. Uma colisão simultânea em ambos é praticamente impossível.
Onde a dispersão brilha
A dispersão permite comparar subcadeias, encontrar repetições e buscar padrões. É uma ferramenta extremamente versátil.
Verificação rápida
Escolha a ferramenta certa para comparar muitas subcadeias com segurança.
Recapitulação: vantagens da dispersão
Agora você consegue transformar cadeias em valores de dispersão polinomial, consultar qualquer subcadeia em O(1) e se proteger contra colisões. 🚀
Perguntas Frequentes
A aula “Hashing Polinomial de Strings” é grátis?
Sim — o texto completo de “Hashing Polinomial de Strings” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Hashing Polinomial de Strings”?
Compare substrings em tempo constante. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Hashing Polinomial de Strings”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Função de Prefixo do KMP
- Hashing Polinomial de Strings
- Função Z para Busca de Padrões
- Tries para Consultas por Prefixo