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])

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

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});
}