!Суффиксное Дерево

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;

#define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define fi first
#define se second

const int INF = 1e9;
const int MAXN = 2e5 + 239;

vector<char> s;
map<int, int> go[MAXN];

int len[MAXN], poses[MAXN], suflink[MAXN];
int root = 0, pos = 0;
int _size = 1, n = 0;

void goDown()
{
    while(pos > len[go[root][s[n - pos]]])
    {
        root = go[root][s[n - pos]];
        pos -= len[root];
    }
}

int f(int curPos, int curLen)
{
    poses[_size] = curPos;
    len[_size] = curLen;
    return _size++;
}

void iter(int c)
{
    n++;
    pos++;
    int last = 0;
    while(pos > 0)
    {
        goDown();
        int edge = s[n - pos];
        int &v = go[root][edge];
        int t = s[poses[v] + pos - 1];
        if(v == 0)
        {
            v = f(n - pos, INF);
            suflink[last] = root;
            last = 0;
        }
        else if(t == c)
        {
            suflink[last] = root;
            return;
        }
        else
        {
            int u = f(poses[v], pos - 1);
            go[u][c] = f(n - 1, INF);
            go[u][t] = v;
            poses[v] += pos - 1;
            len [v] -= pos - 1;
            v = u;
            suflink[last] = u;
            last = u;
        }
        if(root == 0)
            pos--;
        else
            root = suflink[root];
    }
}

int main()
{
   // in("count.in");
   // out("count.out");
    len[0] = INF;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        iter(S[i]);
    return 0;
}