!Суффиксный Автомат

#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 MAXN = 2.3e6, ALF = 26;

int g[MAXN][ALF], suf[MAXN], len[MAXN], last, n;

void iter(int c)
{
    int newLast = n;
    n++;
    int p = last;
    len[newLast] = len[p] + 1;
    while (p != -1 && g[p][c] == -1)
    {
        g[p][c] = newLast;
        p = suf[p];
    }
    if (p == -1)
        suf[newLast] = 0;
    else
    {
        int q = g[p][c];
        if (len[q] == len[p] + 1)
            suf[newLast] = q;
        else
        {
            int r = n;
            n++;
            for (int i = 0; i < ALF; i++)
                g[r][i] = g[q][i];
            suf[r] = suf[q];
            len[r] = len[p] + 1;
            while (p != -1 && g[p][c] == q)
            {
                g[p][c] = r;
                p = suf[p];
            }
            suf[q] = suf[newLast] = r;
        }
    }
    last = newLast;
}

vector<int> term;

int main()
{
   // in("count.in");
   // out("count.out");
    for (int i = 0; i < MAXN; i++)
    {
        suf[i] = -1;
        for (int j = 0; j < ALF; j++)
            g[i][j] = -1;
    }
    n = 1;
    last = 0;
    len[0] = 0;
    suf[0] = -1;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        iter(s[i] - 'a');
    return 0;
}