Suffix Automaton Implementation

/**
 * Author          : Dipu Kumar Mohanto Dip
 *                   CSE, BRUR.
 *                   Batch - 6
 *
 * Problem         : Suffix Automaton Implementation
 * Algorithm       : SAM - Suffix Automaton
 * Complexity      : O(n)
 * Category        : String
 *
 * Difficulty      : Hard
 *
 * Source          : sai sumit
 *                   E-max algo
 *
 * Verdict         : OK
 *
 * Date            :
 * E-mail          : dipukumarmohanto1@gmail.com
**/


#include <bits/stdc++.h>

using namespace std;



struct state {
    int len, link;
    map <char, int> next;
};

const int mx = 1e6+5;

state st[mx<<1];
int sz, last;

void init()
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;

    //clear the structure
    //for (int i=0; i<(mx<<1); i++)
    //{
    //    st[i].next.clear();
    //}
}



void sz_extend(char c)
{
    int curr = sz++;

    st[curr].len = st[last].len + 1;

    int p;

    for (p=last; p != -1 && !st[p].next.count(c); p = st[p].link)
        st[p].next[c] = curr;

    if (p == -1)
        st[curr].link = 0;

    else
    {
        int q = st[p].next[c];

        if (st[p].len + 1 == st[q].len)
            st[curr].link = q;

        else
        {
            int clone = sz++;

            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;

            for ( ; p!=-1 && st[p].next[c] == q; p = st[p].link)
                st[p].next[c] = clone;

            st[q].link = st[curr].link = clone;
        }
    }
    last = curr;
}