Template Suffix Link Trie

// multiple pattern -- a.k.a. aho-corasick
// O( T + P )
string text;
vs pattern;

struct trie{
    vector< trie* > ch;
    trie *sfx; // suffix link: links to the end of the longest matched suffix
    trie *dict_sfx; // links to the end of suffix link where it is a complete pattern
    int index; // index of a complete pattern, if terminated here
    trie(){
        ch.resize( 26 );
        for( int i = 0; i < 26; ++i )
            ch[ i ] = NULL;
        sfx = dict_sfx = NULL;
        index = -1;
    }
};

void insert( trie *root, const string &s, int pid ){
    trie *p = root;
    for( int i = 0; i < s.size(); ++i ){
        if( p->ch[ s[ i ] - 'A' ] == NULL )
            p->ch[ s[ i ] - 'A' ] = new trie();
        p = p->ch[ s[ i ] - 'A' ];
    }
    p->index = pid;
}

void build_sfx_link( trie *root ){
    trie *q[ 1000001 ], **qf, **qb;
    qf = qb = q;
    *qb++ = root;
    while( qf < qb ){
        trie *p = *qf++;
        for( int i = 0; i < 26; ++i )
            if( p->ch[ i ] ){
                trie *q = p->sfx;
                while( q and q->ch[ i ] == NULL )
                    q = q->sfx;
                if( q )
                    p->ch[ i ]->sfx = q->ch[ i ];
                else
                    p->ch[ i ]->sfx = root;

                trie *r = p->ch[ i ]->sfx;
                if( r->index != -1 )
                    p->ch[ i ]->dict_sfx = r;
                else
                    p->ch[ i ]->dict_sfx = r->dict_sfx;

                *qb++ = p->ch[ i ];
            }
    }
}

void match( trie *root, const string &t, vi &occur ){ // t for text
    trie *p = root;
    for( int i = 0; i < t.size(); ++i ){
        while( p and p->ch[ t[ i ] - 'A' ] == NULL )
            p = p->sfx;
        if( p )
            p = p->ch[ t[ i ] - 'A' ];
        else
            p = root;

        for( trie *q = p; q; q = q->dict_sfx )
            if( q->index != -1 )
                occur[ i - pattern[ q->index ].size() + 1 ] = 1;
    }
}

void solve(){
    cin >> text;
    int N; cin >> N;
    for( int i = 0; i < N; ++i ){
        string s; cin >> s;
        pattern.push_back( s );
    }

    trie *root_trie = new trie();
    for( int i = 0; i < N; ++i )
        insert( root_trie, pattern[ i ], i );

    build_sfx_link( root_trie );

    vi occur( text.size() );
    match( root_trie, text, occur );

    vi ans;
    for( int i = 0; i < occur.size(); ++i )
        if( occur[ i ] )
            ans.push_back( i );
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] << " \n"[ i + 1 == ans.size() ];
}