Poj Solution 2774

http://poj.org/problem?id=2774

#include "stdio.h"
#include "memory.h"
#include "string.h"
#include "stdlib.h"



const int CHAR_NUM = 27;
const int MAXSIZE = 500000;

struct suftree{
    suftree *ch[CHAR_NUM];
    char *l, *r;
    int len;
    suftree *s, *p;
}suft[MAXSIZE];

int use_node = 0;

///////////////////////////////////////////////

suftree *new_node( ) {
    memset( suft+use_node, 0, sizeof(suft[0].ch) );
    suft[use_node].s = 0;
    return suft+(use_node++);
}
suftree *proot;

int get_index( char c ) {
    if( c == '$' )
        return CHAR_NUM-1;
    return c-'a';
}

//    ->t    :    ->pnew->t 
suftree *disjoin( suftree *t, char *c ) {
    suftree *pnew = new_node( );

    pnew->len = t->p->len + ( c-t->l );
    pnew->l = t->l;
    pnew->r = c;
    pnew->p = t->p;
    pnew->ch[ get_index( *c ) ] = t;

    t->p->ch[ get_index( *(t->l) ) ] = pnew;

    t->l = c;
    t->p = pnew;

    return pnew;
}

/*
     p ------> s
    /            
   t            sc
*/
void modify_s( suftree *t ) {
    suftree *s, *p, *sc, *pnew;
    int l1, l2;
    char *l, *r;
    
    if( t->s ) return;
    p = t->p;
    s = p->s;

    if( p == proot && t->r-t->l == 1 ) {
        t->s = proot;
        return;
    }

    l = t->l + ( p == proot );
    r = t->r;

    sc = s->ch[ get_index( *l ) ];
    l1 = ( r - l );
    while( l1 ) {
        l2 = ( sc->r - sc->l );
        if( l1 < l2 ) {
            pnew = disjoin( sc, sc->l+l1 );
            t->s = pnew;
            modify_s( pnew );
            return;
        }
        else {
            if( l1 == l2 ) break;
            l1 -= l2;
            sc = sc->ch[ get_index( l[l2] ) ];
            l += l2;
        }
    }

    t->s = sc;
}

/////////////////////////////////////////////////

void create( char *w, int n ) {
    int i, j;
    char *l, *r = w+n+1, *c;
    suftree *h, *t, *tc; 
    use_node = 0;
    proot = new_node( );

    proot->p = proot->s = proot;
    proot->l = proot->r = w;
    proot->len = 0;
    w[n] = '$';
    w[n+1] = '';
    h = proot;

    for( i=0; i<n; i++ ) {
        
        if( i ) {
            l = r - ( h->r - h->l );
            if( l-w < i ) l = w+i;
        }
        else l = w;
        t = h->p->s;        

        while( 1 ) {
            j = get_index( *l );
            tc = t->ch[ j ];

            if( tc == 0 ) {
                tc = new_node( );
                tc->l = l;
                tc->r = r;
                tc->p = t;
                tc->len = t->len + ( r-l );
                t->ch[ j ] = tc;
                modify_s( t );
                break;
            }
            else {
                for( c=tc->l; c<tc->r && *l == *c; c++, l++ )
                    ;
                if( c >= tc->r )
                    t = tc;
                else
                    t = disjoin( tc, c );
            }
        }
        h = tc;

    }//for

}
//////////////////////////////////////////////////////////////////////

char word1[100100], word2[100100];
int main( ) {
    int len1, len2, ans = 0, temp, i;
    char *l, *l1, *l2;
    suftree *t, *tc;

    ans = 0;    
    scanf( "%s", word1 );
    scanf( "%s", word2 );
    len1 = strlen( word1 );
    len2 = strlen( word2 );
    create( word1, len1 );

    t = proot;
    l = word2;
    do {
        tc=t->ch[ get_index(*l) ];
        if( tc ) {
            for( l1=tc->l, l2=l; l1<tc->r && *l1==*l2; l1++, l2++ )
                ;
            if( ( temp = tc->len - ( tc->r-l1 ) ) > ans )
                ans = temp;
            if( l1 == tc->r )
                t = tc, l = l2;
            else {    
                if( t == proot )
                    l++;
                t = t->s;
            }
        }
        else {
            if( t == proot )
                l++;
            t = t->s;
        }
    }while( l < word2+len2 );
    

    printf( "%dn", ans );

    return 0;
}