strings - Suffix Automaton O(n)

/*******************************************************************************************
                            Suffix Automaton
    * A DAG in String Stores all Substring information
    * Complexity : O(n)

    * len[v] -> Maximum length of the string accepted by state v
    * link[v] -> Denotes a state which is a proper suffix of v and in different endpos class
    * SIGMA -> # of different character
    * # of substring accepted by a state = len[v] - len[link[v]]
    * # of different substring = # of different paths in the DAG from root
    * # of occurrence of a string which ends at p = # of paths from p to terminal nodes

*********************************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int N = 25e4+5;
const int SIGMA = 26;
string A;

struct SAM {
    int len[2*N], link[2*N];
    int nxt[2*N][SIGMA];
    int sz,last;
    int SAT[2*N];
    int cnt[2*N];
    bool TerMinal[2*N];
    int dp[2*N];
    int toop[2*N];
    void initTree()
    {
        last= 0;
        len[last] = 0;
        link[last] = -1;
        sz = 1;
        memset(nxt[0],0,sizeof nxt[0]);
    }
    void add(int c,int pos)
    {
        int cur = sz ++ , p = last; memset(nxt[cur],0,sizeof nxt[cur]);
        len[cur] = 1 + len[last];
        last = cur;
        for(; p !=-1 && nxt[p][c] == 0; p = link[p] ) nxt[p][c] = cur;
        if(p==-1) {
            link[cur] = 0;
        }
        else {
            int q = nxt[p][c];
            if(len[q] == 1 + len[p] ) {
                link[cur] = q;
            }
            else {
                int clone = sz ++;
                memcpy(nxt[clone],nxt[q], sizeof(nxt[q]));
                len[clone] = 1 + len[p];
                link[clone] = link[q];
                link[q] = link[cur] = clone;
                for(; p !=-1 &&nxt[p][c]== q ; p = link[p]) nxt[p][c] = clone;
            }
        }
        SAT[pos] = cur;
    }
    void Toop(int n) {
        for (int i = 0; i <= n; i++) cnt[i] = 0;
        for (int i = 1; i < sz; i++) cnt[len[i]]++;
        for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
        for (int i = 1; i < sz; i++) toop[cnt[len[i]]--] = i;
    }
}Solver;
int main()
{
    Solver.initTree();
    cin >> A;
    for(int i = 0;i < A.length() ; i ++ ) {
        Solver.add(A[i]-'A', i );
    }
}