// Subsecuencia común más larga y distancia de edición sobre dos cadenas. Los prefijos son
// semiabiertos: la casilla (i, j) habla de a[0..i) y b[0..j), así que la tabla mide (n+1) x (m+1).
#pragma once

#include <algorithm>
#include <cstddef>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using Table = std::vector<std::vector<int>>;

// lcs[i][j]: el largo de la subsecuencia común más larga de a[0..i) y b[0..j).
inline Table lcs_table(const std::string& a, const std::string& b) {
    Table lcs(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = std::max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }
    return lcs;
}

// Reconstruye una subsecuencia. Ante un empate entre arriba e izquierda, prefer_up decide.
inline std::string lcs_walk(const std::string& a, const std::string& b, const Table& lcs, bool prefer_up) {
    std::string result;
    std::size_t i = a.size();
    std::size_t j = b.size();
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            result.push_back(a[i - 1]);
            i--;
            j--;
        } else if (lcs[i - 1][j] > lcs[i][j - 1] || (lcs[i - 1][j] == lcs[i][j - 1] && prefer_up)) {
            i--;
        } else {
            j--;
        }
    }
    std::reverse(result.begin(), result.end());
    return result;
}

inline bool is_subsequence(const std::string& small, const std::string& big) {
    std::size_t k = 0;
    for (char c : big) {
        if (k < small.size() && small[k] == c) k++;
    }
    return k == small.size();
}

// Prueba las 2^n subsecuencias de a. Solo sirve de árbitro con cadenas cortas.
inline std::size_t lcs_brute(const std::string& a, const std::string& b) {
    std::size_t best = 0;
    for (unsigned mask = 0; mask < (1U << a.size()); mask++) {
        std::string candidate;
        for (std::size_t i = 0; i < a.size(); i++) {
            if ((mask >> i) & 1U) candidate.push_back(a[i]);
        }
        if (is_subsequence(candidate, b)) best = std::max(best, candidate.size());
    }
    return best;
}

// Subcadena común más larga: tiene que ser contigua. run[i][j] es el largo del tramo común que
// termina justo en a[i - 1] y b[j - 1], y la respuesta es el máximo de toda la tabla.
inline std::string longest_common_substring(const std::string& a, const std::string& b) {
    Table run(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    int best = 0;
    std::size_t best_end = 0;
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) {
                run[i][j] = run[i - 1][j - 1] + 1;
                if (run[i][j] > best) {
                    best = run[i][j];
                    best_end = i;
                }
            }
        }
    }
    return a.substr(best_end - static_cast<std::size_t>(best), static_cast<std::size_t>(best));
}

// dist[i][j]: el mínimo de operaciones para convertir a[0..i) en b[0..j).
inline Table edit_table(const std::string& a, const std::string& b) {
    Table dist(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    for (std::size_t i = 0; i <= a.size(); i++) dist[i][0] = static_cast<int>(i);
    for (std::size_t j = 0; j <= b.size(); j++) dist[0][j] = static_cast<int>(j);
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            const int change = a[i - 1] == b[j - 1] ? 0 : 1;
            dist[i][j] = std::min({dist[i - 1][j] + 1,            // borrar a[i - 1]
                                   dist[i][j - 1] + 1,            // insertar b[j - 1]
                                   dist[i - 1][j - 1] + change});  // conservar o cambiar
        }
    }
    return dist;
}

// Una columna del alineamiento. Las posiciones son de las cadenas originales.
struct EditStep {
    enum class Kind { keep, change, erase, insert };
    Kind kind;
    std::size_t i;  // posición en a (no se usa si kind es insert)
    std::size_t j;  // posición en b (no se usa si kind es erase)
};

// Camina hacia atrás desde la esquina. En cada casilla toma una opción que explique su valor.
// Ante un empate prefiere la diagonal, luego borrar y luego insertar.
inline std::vector<EditStep> edit_walk(const std::string& a, const std::string& b, const Table& dist) {
    std::vector<EditStep> steps;
    std::size_t i = a.size();
    std::size_t j = b.size();
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i - 1] == b[j - 1] && dist[i][j] == dist[i - 1][j - 1]) {
            steps.push_back({EditStep::Kind::keep, i - 1, j - 1});
            i--;
            j--;
        } else if (i > 0 && j > 0 && dist[i][j] == dist[i - 1][j - 1] + 1) {
            steps.push_back({EditStep::Kind::change, i - 1, j - 1});
            i--;
            j--;
        } else if (i > 0 && dist[i][j] == dist[i - 1][j] + 1) {
            steps.push_back({EditStep::Kind::erase, i - 1, 0});
            i--;
        } else {
            steps.push_back({EditStep::Kind::insert, 0, j - 1});
            j--;
        }
    }
    std::reverse(steps.begin(), steps.end());
    return steps;
}

// Aplica los pasos a a y devuelve lo que resulta, sin mirar b salvo por los caracteres nuevos.
inline std::string apply_steps(const std::string& a, const std::string& b, const std::vector<EditStep>& steps) {
    std::string out;
    for (const EditStep& s : steps) {
        if (s.kind == EditStep::Kind::keep) out.push_back(a[s.i]);
        if (s.kind == EditStep::Kind::change || s.kind == EditStep::Kind::insert) out.push_back(b[s.j]);
    }
    return out;
}

inline int edit_cost(const std::vector<EditStep>& steps) {
    int cost = 0;
    for (const EditStep& s : steps) {
        if (s.kind != EditStep::Kind::keep) cost++;
    }
    return cost;
}

// Con dos filas basta para el número, pero ya no se puede caminar hacia atrás.
inline int edit_two_rows(const std::string& a, const std::string& b) {
    std::vector<int> previous(b.size() + 1);
    std::vector<int> current(b.size() + 1);
    for (std::size_t j = 0; j <= b.size(); j++) previous[j] = static_cast<int>(j);
    for (std::size_t i = 1; i <= a.size(); i++) {
        current[0] = static_cast<int>(i);
        for (std::size_t j = 1; j <= b.size(); j++) {
            const int change = a[i - 1] == b[j - 1] ? 0 : 1;
            current[j] = std::min({previous[j] + 1, current[j - 1] + 1, previous[j - 1] + change});
        }
        std::swap(previous, current);
    }
    return previous[b.size()];
}

// Árbitro: BFS sobre las cadenas, con la definición misma de una operación (sin alineamientos y
// sin recurrencia). Cadenas de a lo sumo max_length caracteres sobre el alfabeto dado. Con
// allow_change en falso, solo borrar e insertar.
inline int edit_bfs(const std::string& a, const std::string& b, const std::string& alphabet, std::size_t max_length,
                    bool allow_change) {
    std::set<std::string> seen = {a};
    std::queue<std::pair<std::string, int>> pending;
    pending.push({a, 0});
    while (!pending.empty()) {
        const std::string s = pending.front().first;
        const int d = pending.front().second;
        pending.pop();
        if (s == b) return d;
        std::vector<std::string> next;
        for (std::size_t p = 0; p < s.size(); p++) {
            next.push_back(s.substr(0, p) + s.substr(p + 1));
            if (allow_change) {
                for (char c : alphabet) next.push_back(s.substr(0, p) + c + s.substr(p + 1));
            }
        }
        if (s.size() < max_length) {
            for (std::size_t p = 0; p <= s.size(); p++) {
                for (char c : alphabet) next.push_back(s.substr(0, p) + c + s.substr(p));
            }
        }
        for (const std::string& t : next) {
            if (seen.insert(t).second) pending.push({t, d + 1});
        }
    }
    return -1;
}