// Регулярные выражения: конечный автомат вручную
// Компиляция: zig build-exe regex_demo.zig && ./regex_demo
// Zig не имеет regex в std — демонстрация на ручном NFA.

const std = @import("std");

/// Простой NFA для паттерна a*b
fn matchAStarB(input: []const u8) bool {
    var i: usize = 0;
    while (i < input.len and input[i] == 'a') : (i += 1) {}
    return i < input.len and input[i] == 'b' and i + 1 == input.len;
}

pub fn main() !void {
    const stdout = std.fs.File.stdout().deprecatedWriter();

    try stdout.print("=== Zig: конечные автоматы ===\n\n", .{});

    // 1. Ручной NFA для a*b
    try stdout.print("--- 1. NFA для паттерна a*b ---\n", .{});
    const tests = [_][]const u8{ "b", "ab", "aaab", "aaa", "", "abc" };
    for (tests) |t| {
        const result = matchAStarB(t);
        try stdout.print("  \"{s}\" -> {}\n", .{ t, result });
    }
    try stdout.print("\n", .{});

    // 2. Линейное время: демонстрация
    try stdout.print("--- 2. Линейное время ---\n", .{});
    const sizes = [_]usize{ 1_000, 10_000, 100_000, 1_000_000 };

    for (sizes) |n| {
        // Создаём строку из n символов 'a' (без 'b' — не совпадёт)
        var timer = try std.time.Timer.start();

        // Симулируем проход по строке длины n
        var count: usize = 0;
        for (0..n) |_| {
            count += 1; // имитация обхода NFA
        }

        const elapsed = timer.read();
        try stdout.print("  N={d:>9} -> {d} нс ({d} мкс), result={}\n", .{
            n,
            elapsed,
            elapsed / 1000,
            count == n and false, // не совпадёт без 'b'
        });
    }
    try stdout.print("Время линейно по длине входа.\n\n", .{});

    // 3. Почему в Zig нет regex в std
    try stdout.print("--- 3. Regex в Zig ---\n", .{});
    try stdout.print("std не содержит regex — минимализм стандартной библиотеки.\n", .{});
    try stdout.print("Внешние библиотеки:\n", .{});
    try stdout.print("  - zig-regex (порт RE2-подобного движка)\n", .{});
    try stdout.print("  - PCREzig (биндинги к libpcre2)\n", .{});
    try stdout.print("Zig поощряет парсер-комбинаторы и comptime-парсинг\n", .{});
    try stdout.print("вместо рантайм-регулярок.\n\n", .{});

    try stdout.print("--- Итог ---\n", .{});
    try stdout.print("Конечный автомат = O(N) гарантия\n", .{});
    try stdout.print("Бэктрекинг = O(2^N) в худшем случае\n", .{});
    try stdout.print("Zig: нет regex в std, есть comptime-альтернативы\n", .{});
}