---
title: "KMP (Knuth-Morris-Pratt) em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/kmp-knuth-morris-pratt-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/kmp-knuth-morris-pratt-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo KMP de busca em strings implementado em Zig. Pattern matching eficiente com tabela de falhas e código funcional."
date: "2026-02-21"
author: "Zig Brasil"
---

# KMP (Knuth-Morris-Pratt) em Zig — Implementação e Explicação

Aprenda o algoritmo KMP de busca em strings implementado em Zig. Pattern matching eficiente com tabela de falhas e código funcional.


# KMP (Knuth-Morris-Pratt) em Zig — Implementação e Explicação

O algoritmo **KMP (Knuth-Morris-Pratt)** busca ocorrências de um padrão em um texto de forma eficiente, sem retroceder no texto. Ele usa uma **tabela de falhas** (failure function) pré-computada a partir do padrão para pular comparações redundantes.

## Como Funciona

1. **Pré-processamento**: constrói a tabela de falhas `lps[]` (Longest Proper Prefix which is also Suffix)
2. **Busca**: percorre o texto uma vez, usando `lps[]` para saber onde retomar a comparação ao encontrar um mismatch

### Visualização

```
Texto:  "ABABDABACDABABCABAB"
Padrão: "ABABCABAB"

Tabela LPS para "ABABCABAB":
  Padrão: A  B  A  B  C  A  B  A  B
  LPS:    0  0  1  2  0  1  2  3  4

Busca:
  Texto:  A B A B D A B A C D A B A B C A B A B
  Padrão: A B A B C
                  ↑ mismatch em índice 4
                  lps[3]=2, então desloca padrão:

  Texto:  A B A B D A B A C D A B A B C A B A B
  Padrão:     A B A B C
                  ↑ mismatch em D vs A
                  lps[1]=0, continua...

  ...eventualmente encontra match na posição 10:
  Texto:  A B A B D A B A C D [A B A B C A B A B]
  Padrão:                      A B A B C A B A B  ✓
```

## Implementação em Zig

```zig
const std = @import("std");
const Allocator = std.mem.Allocator;

/// Constrói a tabela LPS (Longest Proper Prefix Suffix).
pub fn construirLPS(allocator: Allocator, padrao: []const u8) ![]usize {
    const m = padrao.len;
    const lps = try allocator.alloc(usize, m);
    lps[0] = 0;

    var comprimento: usize = 0;
    var i: usize = 1;
    while (i < m) {
        if (padrao[i] == padrao[comprimento]) {
            comprimento += 1;
            lps[i] = comprimento;
            i += 1;
        } else {
            if (comprimento != 0) {
                comprimento = lps[comprimento - 1];
            } else {
                lps[i] = 0;
                i += 1;
            }
        }
    }

    return lps;
}

/// Busca todas as ocorrências do padrão no texto usando KMP.
/// Retorna as posições iniciais de cada match.
pub fn kmpBusca(
    allocator: Allocator,
    texto: []const u8,
    padrao: []const u8,
) ![]usize {
    if (padrao.len == 0 or texto.len < padrao.len) {
        return try allocator.alloc(usize, 0);
    }

    const n = texto.len;
    const m = padrao.len;

    const lps = try construirLPS(allocator, padrao);
    defer allocator.free(lps);

    var ocorrencias = std.ArrayList(usize).init(allocator);

    var i: usize = 0; // índice no texto
    var j: usize = 0; // índice no padrão
    while (i < n) {
        if (texto[i] == padrao[j]) {
            i += 1;
            j += 1;
        }

        if (j == m) {
            // Match encontrado na posição i-j
            try ocorrencias.append(i - j);
            j = lps[j - 1];
        } else if (i < n and texto[i] != padrao[j]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }

    return try ocorrencias.toOwnedSlice();
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const texto = "ABABDABACDABABCABAB";
    const padrao = "ABABCABAB";

    try stdout.print("Texto:  \"{s}\"\n", .{texto});
    try stdout.print("Padrão: \"{s}\"\n\n", .{padrao});

    // Mostra tabela LPS
    const lps = try construirLPS(allocator, padrao);
    defer allocator.free(lps);
    try stdout.print("Tabela LPS: ", .{});
    for (lps) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    // Busca
    const matches = try kmpBusca(allocator, texto, padrao);
    defer allocator.free(matches);

    try stdout.print("Ocorrências encontradas: {d}\n", .{matches.len});
    for (matches) |pos| {
        try stdout.print("  Posição {d}: \"{s}\"\n", .{
            pos, texto[pos .. pos + padrao.len],
        });
    }

    // Segundo exemplo
    try stdout.print("\n--- Segundo exemplo ---\n", .{});
    const texto2 = "AAAAAA";
    const padrao2 = "AAA";
    const matches2 = try kmpBusca(allocator, texto2, padrao2);
    defer allocator.free(matches2);
    try stdout.print("Texto: \"{s}\", Padrão: \"{s}\"\n", .{ texto2, padrao2 });
    try stdout.print("Matches nas posições: ", .{});
    for (matches2) |pos| try stdout.print("{d} ", .{pos});
    try stdout.print("\n", .{});
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Pré-processamento (LPS)** | O(m) | O(m) |
| **Busca** | O(n) | O(1) |
| **Total** | O(n + m) | O(m) |

Onde n = comprimento do texto e m = comprimento do padrão.

## KMP vs Força Bruta

| Aspecto | Força Bruta | KMP |
|---------|-------------|-----|
| Tempo | O(n * m) | O(n + m) |
| Retrocesso no texto | Sim | Não |
| Pré-processamento | Não | Sim (O(m)) |

## Recursos Relacionados

- [Rabin-Karp](/algoritmos/rabin-karp/) — Busca com hashing de strings
- [Trie — Implementação](/algoritmos/trie-implementacao/) — Busca de múltiplos padrões
- [String Hashing](/algoritmos/string-hashing/) — Hash eficiente de strings
- [Busca Linear](/algoritmos/busca-linear/) — Busca sequencial simples