---
title: "LCS (Maior Subsequência Comum) em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/lcs-maior-subsequ%C3%AAncia-comum-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/lcs-maior-subsequ%C3%AAncia-comum-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo LCS (Longest Common Subsequence) implementado em Zig. Programação dinâmica com código funcional e análise completa."
date: "2026-02-21"
author: "Zig Brasil"
---

# LCS (Maior Subsequência Comum) em Zig — Implementação e Explicação

Aprenda o algoritmo LCS (Longest Common Subsequence) implementado em Zig. Programação dinâmica com código funcional e análise completa.


# LCS (Maior Subsequência Comum) em Zig — Implementação e Explicação

O algoritmo **LCS (Longest Common Subsequence)** encontra a maior subsequência presente em duas sequências. Diferente de substring, uma subsequência não precisa ser contígua — mas deve manter a ordem relativa dos elementos.

## Como Funciona

Dadas duas strings X e Y, construímos uma tabela dp onde dp[i][j] representa o comprimento da LCS de X[0..i] e Y[0..j].

```
Se X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Senão:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```

### Visualização

```
X = "ABCBDAB"    Y = "BDCAB"

Tabela dp:
       ""  B  D  C  A  B
  ""    0  0  0  0  0  0
  A     0  0  0  0  1  1
  B     0  1  1  1  1  2
  C     0  1  1  2  2  2
  B     0  1  1  2  2  3
  D     0  1  2  2  2  3
  A     0  1  2  2  3  3
  B     0  1  2  2  3  4

LCS = "BCAB" (comprimento 4)

Rastreamento (↖ = caractere na LCS):
  Começa em dp[7][5], segue para trás:
  dp[7][5]=4 → B (↖) → dp[6][4]=3 → A (↖) →
  dp[5][3]=2 → dp[4][3]=2 → C (↖) → dp[3][2]=1 →
  dp[2][2]=1 → B (↖) → dp[1][0]=0 → fim
```

## Implementação em Zig

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

/// Resultado da LCS contendo comprimento e a subsequência reconstruída.
pub const ResultadoLCS = struct {
    comprimento: usize,
    subsequencia: []u8,
    allocator: Allocator,

    pub fn deinit(self: *ResultadoLCS) void {
        self.allocator.free(self.subsequencia);
    }
};

/// Calcula a Longest Common Subsequence de duas strings.
pub fn lcs(allocator: Allocator, x: []const u8, y: []const u8) !ResultadoLCS {
    const m = x.len;
    const n = y.len;

    // Aloca tabela dp (m+1) x (n+1)
    const dp = try allocator.alloc([]u16, m + 1);
    defer {
        for (dp) |row| allocator.free(row);
        allocator.free(dp);
    }

    for (dp) |*row| {
        row.* = try allocator.alloc(u16, n + 1);
        @memset(row.*, 0);
    }

    // Preenche a tabela
    for (1..m + 1) |i| {
        for (1..n + 1) |j| {
            if (x[i - 1] == y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = @max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    const comprimento: usize = dp[m][n];

    // Reconstrói a subsequência
    var resultado = try allocator.alloc(u8, comprimento);
    if (comprimento > 0) {
        var idx: usize = comprimento;
        var i: usize = m;
        var j: usize = n;
        while (i > 0 and j > 0) {
            if (x[i - 1] == y[j - 1]) {
                idx -= 1;
                resultado[idx] = x[i - 1];
                i -= 1;
                j -= 1;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i -= 1;
            } else {
                j -= 1;
            }
        }
    }

    return .{
        .comprimento = comprimento,
        .subsequencia = resultado,
        .allocator = allocator,
    };
}

/// Versão otimizada em espaço — apenas o comprimento, sem reconstrução.
pub fn lcsComprimento(allocator: Allocator, x: []const u8, y: []const u8) !usize {
    const n = y.len;

    var anterior = try allocator.alloc(u16, n + 1);
    defer allocator.free(anterior);
    var atual = try allocator.alloc(u16, n + 1);
    defer allocator.free(atual);

    @memset(anterior, 0);

    for (x) |cx| {
        @memset(atual, 0);
        for (1..n + 1) |j| {
            if (cx == y[j - 1]) {
                atual[j] = anterior[j - 1] + 1;
            } else {
                atual[j] = @max(anterior[j], atual[j - 1]);
            }
        }
        const temp = anterior;
        anterior = atual;
        atual = temp;
    }

    return anterior[n];
}

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

    const x = "ABCBDAB";
    const y = "BDCAB";

    var resultado = try lcs(allocator, x, y);
    defer resultado.deinit();

    try stdout.print("X = \"{s}\"\n", .{x});
    try stdout.print("Y = \"{s}\"\n", .{y});
    try stdout.print("LCS = \"{s}\" (comprimento {d})\n", .{ resultado.subsequencia, resultado.comprimento });

    // Versão otimizada em espaço
    const comp = try lcsComprimento(allocator, x, y);
    try stdout.print("Comprimento (espaço otimizado): {d}\n", .{comp});
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Com reconstrução** | O(m * n) | O(m * n) |
| **Apenas comprimento** | O(m * n) | O(min(m, n)) |

Onde m e n são os comprimentos das duas sequências.

## Aplicações

- **Diff de arquivos**: ferramentas como `diff` e `git diff` usam variantes da LCS
- **Bioinformática**: comparação de sequências de DNA/proteínas
- **Controle de versão**: detectar mudanças entre versões de um arquivo
- **Detecção de plágio**: encontrar trechos semelhantes entre textos

## Recursos Relacionados

- [Edit Distance (Levenshtein)](/algoritmos/edit-distance/) — Distância de edição entre strings
- [LIS — Subsequência Crescente](/algoritmos/lis-subsequencia-crescente/) — LCS pode ser reduzida a LIS
- [Knapsack (Mochila)](/algoritmos/knapsack-mochila/) — Outro problema clássico de DP
- [Levenshtein Distance](/algoritmos/levenshtein-distance/) — Métrica de similaridade de strings