后缀自动机模版

struct Suffix_Automaton
{
    int nex[maxn << 1][26], a[maxn << 1], link[maxn << 1];
    int tot, last, root;
    int p, q, np, nq;
    int newnode(int len)
    {
        for (int i = 0; i < 26; ++i) nex[tot][i] = -1;
        link[tot] = -1; a[tot] = len; 
        return tot++;
    }
    void clear()
    {
        tot = last = 0; 
        root = newnode(0);
    }
    void insert(int ch)
    {
        p = last; last = np = newnode(a[p] + 1); 
        for (; ~p && nex[p][ch] == -1; p = link[p]) nex[p][ch] = np;
        if (p == -1) link[np] = root;
        else
        {
            q = nex[p][ch];
            if (a[p] + 1 == a[q]) link[np] = q;
            else
            {
                nq = newnode(a[p] + 1);
                for (int i = 0; i < 26; ++i) nex[nq][i] = nex[q][i];
                link[nq] = link[q];
                link[np] = link[q] = nq;
                for (; ~p && nex[p][ch] == q; p = link[p]) nex[p][ch] = nq;
            }
        }
    }
    long long getSubNum()
    {
        long long ans = 0;
        for (int i = 1; i < tot; ++i) ans += a[i] - a[link[i]];
        return ans;
    }
}sam;