#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define int long long
#define p_b push_back

struct vertex
{
    vector<int> out; // исходящие ребра
    bool leaf;  //флаг есть ли конец слова
    char cur_sym;//символ входящего ребра
    string word;
    int inp;
};

struct correct
{
    string correct_word;
    int end_mistakes = 0;
};
struct chip
{
    int index_ver;
    int letter;
    int mistakes = 0;
};

vector<correct> listt;
vector<vertex> bor;
vector<chip> first;
vector<chip> second;

template<typename T> //заголовочный файл!
class Slovar {
public:
    void push(const string& word, const T& data);
    bool check(const string& word);
};

//добавление строки
void push(const string& word, int position, int bor_index) { //position позиция в слове, bor_index место где мы в дереве бора

    //проверка на лист(конец слова)
    if (position == word.size()) {
        bor[bor_index].leaf = true;
        bor[bor_index].word = word;
        return;
    }

    //перебор всех рёбер
    for (int i = 0; i < bor[bor_index].out.size(); i++) {
        if (word[position] == bor[bor[bor_index].out[i]].cur_sym) {
            push(word, position + 1, bor[bor_index].out[i]);
            return;
        }
    }

    //добавление недостоющей вершины
    vertex new_vertex;
    new_vertex.cur_sym = word[position];
    new_vertex.leaf = false;
    bor.p_b({ new_vertex });
    bor[bor_index].out.p_b(bor.size() - 1);
    bor[bor.size() - 1].inp = bor_index;//??
    push(word, position + 1, bor.size() - 1);
}

int prov = 0;
//поиск слова в словаре(боре)
void search(const string & word, int position, int bor_index)
{
    if ((position == word.size()) && (bor[bor_index].leaf == true)) {
        prov = 1;
        return;
    }

    //смотрим все ребра
    for (int i = 0; i < bor[bor_index].out.size(); i++) {
        if (word[position] == bor[bor[bor_index].out[i]].cur_sym) {
            search(word, position + 1, bor[bor_index].out[i]);
            return;
        }
    }
    prov = -1;
}
int k = 0;
int p = 0;

//исправление ошибок
void typos(const string& word, vector<chip>& first, int max_typos) {

    for (int i = 0; i < first.size(); i++) { // по всем вершинам 1 слоя, пусть нам дан этот массив
        for (int j = 0; j < bor[first[i].index_ver].out.size(); j++) { // по всем ребрам каждого элемента 1 ого массива
            chip new_chip; // создаем новую вишку 2ого уровня
            new_chip.index_ver = bor[first[i].index_ver].out[j]; // вершина этой фишки исходящие ребро j(из выходящих ребер) из вершины i
            new_chip.letter = first[i].letter + 1;// позиция в слове сместится на 1

            if (word[first[i].letter] != bor[bor[first[i].index_ver].out[j]].cur_sym) { // если прочитанная буква была норм, то оставим ошибки на месте иначе прибавим 1
                new_chip.mistakes = first[i].mistakes + 1;
            }
            else new_chip.mistakes = first[i].mistakes;

            if ((new_chip.mistakes <= max_typos) && (new_chip.letter == word.size()) && (bor[new_chip.index_ver].leaf == true)) //проверяем есть ли в этой новой фишке уонец всего
            {
                listt[k].correct_word = bor[new_chip.index_ver].word;
                listt[k].end_mistakes = new_chip.mistakes;
                k++;
            }
            second.p_b({ new_chip }); // пишем все такие вишки в массив второго уровня
            p++;
            if (p == bor.size()) {
                return;
            }
        }
    }
    typos(word, second, max_typos);
    return;
}
signed main()
{
    bor.resize(1);
    bor[0].leaf = false;
    listt.resize(1);

    first.resize(1);
    first[0].index_ver = 0;
    first[0].letter = 0;
    first[0].mistakes = 0;

    second.resize(0);

    string test = "privetik";
    string test1 = "privw";
    string test22 = "hasvddik";
    push(test, 0, 0);
    push(test1, 0, 0);
    for (int i = 0; i < bor.size(); i++) {
        cout << bor[i].cur_sym << '\n';
    }
    search(test1, 0, 0);
    typos(test22, first, test22.size()/2);
    for (int i = 0; i < listt.size(); i++) {
        cout << listt[i].correct_word << listt[i].end_mistakes << '\n';
    }
    //cout << prov << '\n';
}