Пусть утро будет нежным!

Сидя у себя в офисе в Калифорнии, Марк Цукерберг чуть не подавился молочным латте без лактозы, когда увидел какое количество памяти занимают картинки с добрым утром вашей бабушки в WhatsApp. В скором порядке он созвал внезапную планерку талантливейших кодировщиков со всего мира, где единогласно пришли к решению о сжатии всех картинок через алгоритм LZ78.

Входные данные

Строка 
s
s (
∣
s
∣
≤
∣s∣≤ 
5
∗
1
0
5
5∗10 
5
 ) , состоящая из строчных латинских букв, обозначающая метаданные файла, который необходимо сжать.

Выходные данные

На каждой новой строчке необходимо последовательно вывести список пар
p
o
s
pos и 
n
e
x
t
next, где 
p
o
s
pos - номер в словаре самого длинного найденного префикса и 
n
e
x
t
next - символ, который следует за этим префиксом. #include <iostream>
#include <vector>
#include <string>

struct Node{
    int pos;
    char next;
};

struct Dict{
    int ind = 0;
    std::string word;
    int pos;
    int height = 1;
    Dict* left = nullptr;
    Dict* right = nullptr;
};

int GetHeight(Dict* temp) {
    if (temp == nullptr) {
        return 0;
    }

    return temp->height;
}

Dict* LeftRotate(Dict* temp) {
    Dict* new_root = temp->right;
    Dict* new_child = new_root->left;
    new_root->left = temp;
    temp->right = new_child;
    if (GetHeight(temp->left) > GetHeight(temp->right)) {
        temp->height = GetHeight(temp->left) + 1;
    } else {
        temp->height = GetHeight(temp->right) + 1;
    }
    if (GetHeight(new_root->left) > GetHeight(new_root->right)) {
        new_root->height = GetHeight(new_root->left) + 1;
    } else {
        new_root->height = GetHeight(new_root->right) + 1;
    }

    return new_root;
}

Dict* RightRotate(Dict* temp) {
    Dict* new_root = temp->left;
    Dict* new_child = new_root->right;
    new_root->right = temp;
    temp->left = new_child;
    if (GetHeight(temp->left) > GetHeight(temp->right)) {
        temp->height = GetHeight(temp->left) + 1;
    } else {
        temp->height = GetHeight(temp->right) + 1;
    }
    if (GetHeight(new_root->left) > GetHeight(new_root->right)) {
        new_root->height = GetHeight(new_root->left) + 1;
    } else {
        new_root->height = GetHeight(new_root->right) + 1;
    }

    return new_root;
}

int GetBalance(Dict* temp) {
    if (temp == nullptr) {
        return 0;
    }

    return GetHeight(temp->left) - GetHeight(temp->right);
}

Dict* Balance(Dict* temp) {
    if (GetHeight(temp->left) > GetHeight(temp->right)) {
        temp->height = GetHeight(temp->left) + 1;
    } else {
        temp->height = GetHeight(temp->right) + 1;
    }
    int balance = GetBalance(temp);
    if (balance < -1 && GetBalance(temp->right) > 0) {
        temp->right = RightRotate(temp->right);
        return LeftRotate(temp);
    }
    if (balance < -1 && GetBalance(temp->right) <= 0) {
        return LeftRotate(temp);
    }
    if (balance > 1 && GetBalance(temp->left) < 0) {
        temp->left = LeftRotate(temp->left);
        return RightRotate(temp);
    }
    if (balance > 1 && GetBalance(temp->left) >= 0) {
        return RightRotate(temp);
    }

    return temp;
}

Dict* Insert(Dict* temp, int pos, std::string word, int& ind) {
    if (temp == nullptr) {
        temp = new Dict();
        temp->pos = pos;
        temp->ind = ind;
        ++ind;
        return temp;
    }
    if (word > temp->word) {
        temp->right = Insert(temp->right, pos, word, ind);
    } else {
        temp->left = Insert(temp->left, pos, word, ind);
    }

    return Balance(temp);
}

bool Exists(Dict* temp, std::string word) {
    while (temp != nullptr) {
        if (word > temp->word) {
            temp = temp->right;
        } else if (word < temp->word) {
            temp = temp->left;
        } else {
            return true;
        }
    }
    return false;
}

int FindPos(Dict* temp, std::string word) {
    while (temp != nullptr) {
        if (word > temp->word) {
            temp = temp->right;
        } else if (word < temp->word) {
            temp = temp->left;
        } else {
            return temp->ind;
        }
    }
    return -1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::string s;
    std::cin >> s;
    std::string buffer = "";
    Dict* root = nullptr;
    int ind = 0;
    std::vector<Node*> answer;
    for (int i = 0; i < s.length(); ++i) {
        if (Exists(root, buffer + s[i])) {
            buffer += s[i];
        } else {
            int pos = FindPos(root, buffer);
            Node* newNode = new Node();
            newNode->pos = pos;
            newNode->next = s[i];
            answer.push_back(newNode);
            root = Insert(root, pos, buffer + s[i], ind);
            buffer = "";
        }
    }
    if (!buffer.empty()) {
        Node* newNode = new Node();
        int pos = FindPos(root, buffer);
        newNode->pos = pos;
        answer.push_back(newNode);
    }
    std::cout << answer[0]->pos << " " << answer[0]->next;
    for (int i = 1; i < answer.size(); ++i) {
        std::cout << '\n' << answer[i]->pos << " " << answer[i]->next;
    }

    return 0;
}
 why when input is abcaba it returns -1 a
0 b
0 c
1 a
1 b
1 a instead of 0 a
0 b
0 c
1 b
1