Suffix Tree

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <unordered_set>
#include <set>
#include <map>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <sstream>
#include <clocale>

using namespace std;



struct vertex {
    struct edge {
        int l, siz;
        vertex* to;
        edge(int l = 0, int siz = 0, vertex* to = nullptr) : l(l), siz(siz), to(to) {}
    };
    vertex* par;
    char par_c;
    map<char, edge> links;
    map<char, vertex*> pref_links;
    vertex(vertex* par = nullptr) : par(par) {}
};

void build(string& s, vertex* t) {
    s.push_back('$');
    int n = s.length();
    vertex* last_vertex = t;
    vector<vertex*> stack;
    stack.reserve(n);
    for (int i = n - 1; i > -1; i--) {
        int now_height = n - i;
        while (!last_vertex->pref_links.count(s[i])) {
            stack.push_back(last_vertex);
            now_height -= last_vertex->par->links[last_vertex->par_c].siz;
            last_vertex = last_vertex->par;
        }

        vertex* w = last_vertex->pref_links[s[i]];
        int to_split = 0;
        if (!w->links.count(s[i + now_height])) {
            vertex* tmp = new vertex(w);
            tmp->par_c = s[i + now_height];
            w->links[s[i]] = vertex::edge(i, n - i - now_height, tmp);
            stack[0]->pref_links[s[i]] = tmp;
            last_vertex = tmp;
            stack.clear();
            continue;
        }
        //if ((*stack.rbegin())->par_c == '$')
        //  stack.pop_back();
        vertex::edge u = w->links[s[i + now_height]];
        vertex* last = nullptr;
        int a = 0;
        for (; !stack.empty() && s[i + now_height] == s[u.l + to_split];) {
            a = (*stack.rbegin())->par->links[(*stack.rbegin())->par_c].siz;
            to_split += a;
            now_height += a;
            last = stack.back();
            stack.pop_back();
        }
        stack.push_back(last);
        if (to_split == 0) {
            vertex* tmp = new vertex(w);
            tmp->par_c = s[i + now_height];
            w->links[s[i + now_height]] = vertex::edge(i + now_height, n - i - now_height, tmp);
            if (!stack.empty())
                stack[0]->pref_links[s[i]] = tmp;
            last_vertex = tmp;
        }
        else {
            vertex* tmp = new vertex(w);
            vertex* tmp2 = new vertex(w);
            tmp2->links[s[u.l + to_split]] = vertex::edge(u.l + to_split, w->links[s[i + now_height]].siz - to_split, u.to);
            u.to->par = tmp2;
            u.to->par_c = s[u.l + to_split];
            w->links[s[i + now_height]].siz = to_split;
            w->links[s[i + now_height]].to = tmp2;
            tmp2->par_c = s[u.l];
            tmp2->links[s[i + now_height]] = vertex::edge(i + now_height, (n - i) - (now_height + 1 - to_split), tmp);
            tmp->par_c = s[i + now_height];
            tmp->par = tmp2;
            (*stack.rbegin())->pref_links[s[i]] = tmp2;
            stack[0]->pref_links[s[i]] = tmp;
            last_vertex = tmp;
        }

        stack.clear();
    }
}

signed main() {
    string s;
    vertex* fictive = new vertex();
    vertex* t = new vertex();
    for (char i = 'A'; i < 'z'; i++) {
        fictive->pref_links[i] = t;
        fictive->links[i] = vertex::edge(0, 1, t);
    }
    t->par_c = 'A';
    t->par = fictive;
    fictive->pref_links['$'] = t;
    //cin >> s;
    s = "mississippi";
    build(s, t);
    t;
    return 0;
}