Template Suffix Tree ( Ukkonen's Algorithm )

search - Ukkonen's suffix tree algorithm in plain English? - Stack Overflow
Suffix tree. Ukkonen's algorithm - Codeforces

struct suffix_tree{
    char s[ MAXN ];
    map< int, int > to[ MAXN ];
    int len[ MAXN ], fpos[ MAXN ], link[ MAXN ];
    int node, pos;
    int sz, n;
    suffix_tree(){
        len[ 0 ] = INF;
        sz = 1, n = 0;
    }
    int make_node( int _pos, int _len ){
        fpos[ sz ] = _pos;
        len[ sz ] = _len;
        return sz++;
    }
    void go_edge(){
        while( pos > len[ to[ node ][ s[ n - pos ] ] ] )
            node = to[ node ][ s[ n - pos ] ],
            pos -= len[ node ];
    }
    void add_letter( int c ){
        s[ n++ ] = c;
        ++pos;
        int last = 0;
        while( pos > 0 ){
            go_edge();
            int edge = s[ n - pos ];
            int &v = to[ node ][ edge ];
            int t = s[ fpos[ v ] + pos - 1 ];
            if( v == 0 ){
                v = make_node( n - pos, INF );
                link[ last ] = node;
                last = 0;
            } else if( t == c ){
                link[ last ] = node;
                return;
            } else{
                int u = make_node( fpos[ v ], pos - 1 );
                to[ u ][ c ] = make_node( n - 1, INF );
                to[ u ][ t ] = v;
                fpos[ v ] += pos - 1;
                len[ v ] -= pos - 1;
                v = u;
                link[ last ] = u;
                last = u;
            }
            if( node == 0 )
                --pos;
            else
                node = link[ node ];
        }
    }
};

void solve(){
    suffix_tree *sfxt = new suffix_tree();
    string s; cin >> s;
    for( int i = 0; i < s.size(); ++i )
        sfxt->add_letter( s[ i ] );
    for( int i = 1; i < sfxt->sz; ++i ) // prints all edges
        cout << s.substr( sfxt->fpos[ i ], sfxt->len[ i ] ) << "\n";
}