Função Z para Busca de Padrões
Compare prefixos ao longo da string.
Função Z para Busca de Padrões é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Outra ferramenta de correspondência
A função Z é uma alternativa simples ao KMP para buscar padrões. Muitas pessoas acham mais fácil raciocinar sobre ela. ✨
O que z[i] significa
Para cada índice, z[i] é o comprimento da maior subcadeia que começa em i e também corresponde a um prefixo da cadeia inteira.
Um pequeno exemplo
Para aabaab, z é 0,1,0,3,1,0. No índice 3, o trecho aab corresponde ao prefixo, produzindo comprimento 3.
A caixa Z
Acompanhamos uma janela [l, r], a correspondência mais à direita encontrada até então. Isso permite reutilizar comparações anteriores.
l, r = 0, 0Dentro da caixa
Quando i está dentro da caixa, você pode copiar um valor de z conhecido como ponto de partida, limitado pela borda da caixa.
if i < r:
z[i] = min(r - i, z[i - l])Indo além da caixa
Depois desse ponto de partida, continue comparando os caracteres um a um enquanto eles corresponderem ao prefixo.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Deslizando a caixa para a frente
Se sua correspondência chegar mais à direita, atualize l e r para que índices futuros possam reutilizá-la.
if i + z[i] > r:
l, r = i, i + z[i]Garantia de tempo linear
A caixa só se move para a direita, então o trabalho total é O(n). Cada caractere contribui com uma quantidade limitada de trabalho.
Buscando com Z
Concatene pattern + sep + text e execute Z. Qualquer valor de z igual ao comprimento do padrão indica uma correspondência.
combined = pattern + chr(0) + text
z = z_function(combined)Identificando as correspondências
Percorra o vetor Z; sempre que z[i] == len(pattern), a correspondência começa no ponto correspondente da cadeia.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z versus KMP
Z e KMP são executados em tempo linear. Z costuma ser mais simples de programar, por isso é uma ótima alternativa para sua caixa de ferramentas.
Verificação rápida
Certifique-se de que você fixou o significado do vetor Z.
Recapitulação: vantagens da função Z
Você construiu o vetor Z com uma caixa deslizante, fez uma busca em tempo linear e agora tem uma alternativa simples ao KMP. 🎯
Perguntas Frequentes
A aula “Função Z para Busca de Padrões” é grátis?
Sim — o texto completo de “Função Z para Busca de Padrões” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Função Z para Busca de Padrões”?
Compare prefixos ao longo da string. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 3 de 4.
Quanto tempo leva a aula “Função Z para Busca de Padrões”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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