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  ✓

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", .{});
}