Distância entre "gato" e "rato":

       ""  r  a  t  o
  ""    0  1  2  3  4
  g     1  1  2  3  4
  a     2  2  1  2  3
  t     3  3  2  1  2
  o     4  4  3  2  1

Distância = 1 (substituir g → r)
Similaridade = 1 - 1/4 = 0.75 (75%)

Distância entre "abacaxi" e "abacate":

       ""  a  b  a  c  a  t  e
  ""    0  1  2  3  4  5  6  7
  a     1  0  1  2  3  4  5  6
  b     2  1  0  1  2  3  4  5
  a     3  2  1  0  1  2  3  4
  c     4  3  2  1  0  1  2  3
  a     5  4  3  2  1  0  1  2
  x     6  5  4  3  2  1  1  2
  i     7  6  5  4  3  2  2  2

Distância = 2, Similaridade = 1 - 2/7 ≈ 0.71 (71%)

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

/// Calcula a distância de Levenshtein entre duas strings.
/// Usa espaço otimizado O(min(m,n)).
pub fn levenshtein(allocator: Allocator, s: []const u8, t: []const u8) !u32 {
    // Otimização: usar a string menor como coluna
    var curto = s;
    var longo = t;
    if (curto.len > longo.len) {
        const tmp = curto;
        curto = longo;
        longo = tmp;
    }

    const m = curto.len;
    const n = longo.len;

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

    for (0..m + 1) |i| {
        anterior[i] = @intCast(i);
    }

    for (0..n) |j| {
        atual[0] = @intCast(j + 1);
        for (0..m) |i| {
            const custo: u32 = if (curto[i] == longo[j]) 0 else 1;
            atual[i + 1] = @min(
                @min(anterior[i + 1] + 1, atual[i] + 1),
                anterior[i] + custo,
            );
        }
        const temp = anterior;
        anterior = atual;
        atual = temp;
    }

    return anterior[m];
}

/// Calcula a similaridade normalizada (0.0 a 1.0).
pub fn similaridade(allocator: Allocator, s: []const u8, t: []const u8) !f64 {
    if (s.len == 0 and t.len == 0) return 1.0;
    const dist = try levenshtein(allocator, s, t);
    const max_len: f64 = @floatFromInt(@max(s.len, t.len));
    return 1.0 - @as(f64, @floatFromInt(dist)) / max_len;
}

/// Busca fuzzy: encontra as strings mais próximas do alvo.
pub fn buscaFuzzy(
    allocator: Allocator,
    alvo: []const u8,
    candidatos: []const []const u8,
    max_distancia: u32,
) ![]struct { texto: []const u8, distancia: u32 } {
    const Resultado = struct { texto: []const u8, distancia: u32 };
    var resultados = std.ArrayList(Resultado).init(allocator);

    for (candidatos) |candidato| {
        const dist = try levenshtein(allocator, alvo, candidato);
        if (dist <= max_distancia) {
            try resultados.append(.{ .texto = candidato, .distancia = dist });
        }
    }

    // Ordena por distância
    const items = resultados.items;
    std.mem.sort(Resultado, items, {}, struct {
        fn f(_: void, a: Resultado, b: Resultado) bool {
            return a.distancia < b.distancia;
        }
    }.f);

    return try resultados.toOwnedSlice();
}

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

    // Exemplos de distância
    const pares = [_][2][]const u8{
        .{ "gato", "rato" },
        .{ "abacaxi", "abacate" },
        .{ "zig", "zag" },
        .{ "programacao", "programando" },
    };

    for (pares) |par| {
        const dist = try levenshtein(allocator, par[0], par[1]);
        const sim = try similaridade(allocator, par[0], par[1]);
        try stdout.print("\"{s}\" ↔ \"{s}\": distância={d}, similaridade={d:.1}%\n", .{
            par[0], par[1], dist, sim * 100,
        });
    }

    // Busca fuzzy (corretor ortográfico)
    try stdout.print("\n--- Corretor ortográfico ---\n", .{});
    const dicionario = [_][]const u8{
        "programar",   "programa",   "programacao",
        "compilar",    "compilador", "variavel",
        "funcao",      "algoritmo",  "estrutura",
    };

    const digitado = "programr";
    const sugestoes = try buscaFuzzy(allocator, digitado, &dicionario, 2);
    defer allocator.free(sugestoes);

    try stdout.print("Digitado: \"{s}\"\n", .{digitado});
    try stdout.print("Sugestões:\n", .{});
    for (sugestoes) |sug| {
        try stdout.print("  \"{s}\" (distância: {d})\n", .{ sug.texto, sug.distancia });
    }
}